【LeetCode系列】：数据结构——数组

🌍数组系列

T：合并区间
T：存在重复元素
T：最大子数组和
T：所有奇数长度子数组的和
- 📚题目详情
- 💡解题思路

T：合并区间

📚题目详情

💡解题思路

如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的：

🔑源代码

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            //如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {//否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
               merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

T：存在重复元素

题目链接：217. 存在重复元素

📚题目详情

💡解题思路

🧠方法一：排序

在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

🔑源代码

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]==nums[i+1]){
                return true;
            }
        }
        return false;
    }
}

☕️复杂度分析

时间复杂度：O(NlogN)，其中 N 为数组的长度。需要对数组进行排序。
空间复杂度：O(logN)，其中 N 为数组的长度。注意我们在这里应当考虑递归调用栈的深度。

🧠方法二：哈希表

对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。

🔑源代码

//Hashset:1.无序；2.不能有重复值
class s2{
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}

T：最大子数组和

题目链接：53. 最大子数组和

📚题目详情

💡解题思路

这道题用动态规划的思路并不难解决

动态规划的是首先对数组进行遍历，当前最大连续子序列和为pre，结果为maxAns.
如果pre > 0，则说明pre对结果有增益效果，则pre保留并加上当前遍历数字
如果pre <= 0，则说明pre对结果无增益效果，需要舍弃，则pre直接更新为当前遍历数字
每次比较pre和maxAns的大小，将最大值置为maxAns，遍历结束返回结果
时间复杂度:O(n)

🔑源代码

class Solution {
        public int maxSubArray(int[] nums) {
            int pre = 0, maxAns = nums[0];
            for (int x : nums) {
                pre = Math.max(pre + x, x);//比较当前元素和之前pre加上当前元素的大小，得到较大值
                maxAns = Math.max(maxAns, pre);//将得到的较大值和之前保存的较大值进行比较
            }
            return maxAns;
        }
    }