第3章 数组

查询修改O(1) 增删O(n)

3. 求三数之和

先排序 然后循环一遍

除了第一遍以外 调过重复的元素 然后双指针向内夹逼

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1] && nums[i] <= 0)) {
                int lo = i + 1, hi = nums.length -1, sum = 0 - nums[i];
                while (lo < hi) {
                    if (nums[lo] + nums[hi] == sum) {
                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                        while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                        lo++; hi--;
                    } else if (nums[lo] + nums[hi] < sum) {
                        lo++;
                    } else {
                        hi--;
                    } 
                }
            }           
        }
        return res;
    }
}

7. 爬楼梯

// 1：1
// 2: 2
// 3: 3
// 4：5
// f(n) = f(n-1) + f(n-2)
class Solution {
    public int climbStairs(int n) {
        if (n < 3) return n;
        int x1 = 1;
        int x2 = 2;
        int x3 = 3;
        for (int i = 0; i < n - 3; i++) {
            x3 = x2 + x3;
            x1 = x2;
            x2 = x3 - x2;           
        }
        return x3;
    }
}

11. 盛水最多的容器

// 1.暴力求解 两次选好 并记录最高的 会超时
// 2.双指针 左右夹逼
class Solution {
    public int maxArea(int[] height) {
       int max = 0;
       //双指针往中间夹逼
       for (int i = 0, j = height.length - 1; i != j; ) {
           int area = (j - i) * Math.min(height[i], height[j]);
           max = max > area ? max : area;
           //谁矮谁往前走
           if (height[i] < height[j]) {
               i++;
           } else {
               j--;
           }
       }
       return max;
    }
}

66. 加一

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length -1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}

88. 合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m + n - 1;
        int j = m - 1;
        int k = n - 1;
        while (j >= 0 && k >= 0) {
            if (nums1[j] > nums2[k]) {
                nums1[i--] = nums1[j--];
            } else {
                nums1[i--] = nums2[k--];
            }
        }
        while (k >= 0) {
            nums1[i--] = nums2[k--];
        }
    }
}

189. 选择数组

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length -1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}

283. 零移动

// 1. 新数组 最优解 但是题目禁止 O(n)
// 2. 循环一次 把大于0的往前挪 最后补领 O(n)
// 3. 双指针 一个指向下一个等于0的数 另一个指向第一个指针下一个不等于0的数 不断循环 直到超出界限
//第二种解法
class Solution {
    public void moveZeroes(int[] nums) {
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) nums[insertPos++] = num; 
        }
        while (insertPos < nums.length) {
            nums[insertPos++] = 0;
        }
    }
}

// 1. 新数组 最优解 但是题目禁止 O(n)
// 2. 循环一次 把大于0的往前挪 最后补领 O(n)
// 3. 双指针 一个指向下一个等于0的数 另一个指向第一个指针下一个不等于0的数 不断循环 直到超出界限
// 第三种解法
class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        int right = 0;
        int len = nums.length;
        while (true) {
            while (left < len && nums[left] != 0) left++;
            right = left + 1;
            while (right < len && nums[right] == 0) right++;
            if (left == len || right == len) break;
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
}