Leetcode数组I

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int minus = target - nums[i];
            if (map.containsKey(minus)) {
                return new int[]{map.get(minus), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[0];
    }
}

两个数组的大小是m和n，找到第(m+n+1)/2和第(m+n+2)/2个数，取其平均值就是中位数。
定义一个函数findKth找到两个数组中第k小的数。
分别在nums1和nums2中查找第K/2个元素，有可能某个数组没有第K/2个数字，如果存在就取出来，否则就赋值上一个整型最大值。如果某个数组没有第K/2个数字，那么我们就淘汰另一个数组的前K/2个数字即可。
比较这两个数组的第K/2小的数字midVal1和midVal2的大小，如果第一个数组的第K/2个数字小的话，那么说明我们要找的数字肯定不在nums1中的前K/2个数字，所以我们可以将其淘汰，将nums1的起始位置向后移动K/2个，并且此时的K也自减去K/2，调用递归。反之，我们淘汰nums2中的前K/2个数字，并将nums2的起始位置向后移动K/2个，并且此时的K也自减去K/2，调用递归即可。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    //i: nums1的起始位置 j: nums2的起始位置
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) return nums2[j + k - 1];//nums1为空数组
        if (j >= nums2.length) return nums1[i + k - 1];//nums2为空数组
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
}

11. 盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        int lo = 0, hi = height.length - 1;
        while (lo < hi) {
            if (height[lo] < height[hi]) {
                res = Math.max(res, height[lo] * (hi - lo));
                lo++;
            } else {
                res = Math.max(res, height[hi] * (hi - lo));
                hi--;
            }
        }
        return res;
    }
}

15. 三数之和

使用回溯，但是某些案例会超时。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfs(int begin, int sum, int[] nums) {
        if (temp.size() == 3 && sum == 0) {
            res.add(new ArrayList<>(temp));
            return;
        } else if (temp.size() == 3 && sum != 0) {
            return;
        }
        for (int i = begin; i < nums.length; i++) {
            if (i - 1 >= begin && nums[i] == nums[i - 1]) {
                continue;
            }
            temp.add(nums[i]);
            dfs(i + 1, sum + nums[i], nums);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        dfs(0, 0, nums);
        return res;
    }
}

转为两数之和：
不能用哈希表做，还是会超时。
只能先对数组排序，再使用二分做，注意去重。

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 - 1 >= 0 && nums[i] == nums[i - 1]) {//去重
                continue;
            }
            int target = -nums[i];
            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                if (nums[lo] + nums[hi] > target) {
                    hi--;
                } else if (nums[lo] + nums[hi] < target) {
                    lo++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    lo++;
                    hi--;
                    while (lo < nums.length && nums[lo] == nums[lo - 1]) {//去重
                        lo++;
                    }
                    while (hi > i && nums[hi] == nums[hi + 1]) {//去重
                        hi--;
                    }
                }
            }
        }
        return res;
    }
}

16. 最接近的三数之和

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            int lo = i + 1, hi = nums.length - 1, sum = target - nums[i], diff = 0;
            while (lo < hi) {
                if (nums[lo] + nums[hi] > sum) {
                    diff = nums[i] + nums[lo] + nums[hi] - target;
                    hi--;
                } else if (nums[lo] + nums[hi] < sum) {
                    diff = nums[i] + nums[lo] + nums[hi] - target;
                    lo++;
                } else {
                    return target;
                }
                if (Math.abs(diff) < Math.abs(minDiff)) {
                    minDiff = diff;
                }
            }
        }
        return target + minDiff;
    }
}

18. 四数之和

和三数之和类似。

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

26. 删除排序数组中的重复项

使用pos记录待覆盖的位置，只把不重复的元素覆盖到数组中。

class Solution {
    public int removeDuplicates(int[] nums) {
        int pos = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            nums[pos++] = nums[i];
        }
        return pos;
    }
}

27. 移除元素

和上一题类似，使用pos记录待覆盖的位置。

class Solution {
    public int removeElement(int[] nums, int val) {
        int pos = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                continue;
            } else {
                nums[pos++] = nums[i];
            }
        }
        return pos;
    }
}

31. 下一个排列

先从右往左找到第一个不是单调递增的数。比如34987， 4就是第一个不是单调递增的数，记录它的位置index。
如果index等于-1，说明整个数从右往左是单调递增的，下一个排列就是把整个数反转一下，比如 98765的下一个排列就是56789。
对于79654，index = 0，它的下一个排列是94567，观察是将7与9交换之后，再把最后4个数反转一下得到的。
所以要从右往左找到第一个比index指向的数大的数，与index交换，然后反转index右边的数即可。

class Solution {
    public void nextPermutation(int[] nums) {
        int index;
        for (index = nums.length - 2; index >= 0; index--) {
            if (nums[index] < nums[index + 1]) {
                break;
            }
        }

        if (index == -1) {
            reverse(nums, 0, nums.length - 1);
        } else {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[index]) {
                j--;
            }
            swap(nums, index, j);
            reverse(nums, index + 1, nums.length - 1);
        }
    }

    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public void reverse(int[] nums, int a, int b) {
        while (a < b) {
            swap(nums, a, b);
            a++;
            b--;
        }
    }
}

33. 搜索旋转排序数组

如果中间的数大于等于最左边的数，则左半段是有序的，若中间数小于等于最右边数，则右半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了。

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] >= nums[lo]) {//左半段有序
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {//右半段有序
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

模板题，考察lowerBound和upperBound函数。

class Solution {
    //返回第一个大于等于target的数
    int lowerBound(int[] nums, int lo, int hi, int target) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
    //返回第一个大于target的数
    int upperBound(int[] nums, int lo, int hi, int target) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int pos1 = lowerBound(nums, 0, nums.length, target);
        int pos2 = upperBound(nums, 0, nums.length, target) - 1;
        if (pos1 >= nums.length || nums[pos1] != target) {
            return new int[]{-1, -1};
        } else {
            return new int[]{pos1, pos2};
        }
    }
}

35. 搜索插入位置

考察lowerBound函数

class Solution {
    public int lowerBound(int[] nums, int lo, int hi, int target) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] >= target) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    public int searchInsert(int[] nums, int target) {
        return lowerBound(nums, 0, nums.length, target);
    }
}

39. 组合总和

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfs(int begin, int sum, int[] candidates, int target) {
        if (sum > target) {
            return;
        } else if (sum == target) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = begin; i < candidates.length; i++) {
            temp.add(candidates[i]);
            dfs(i, sum + candidates[i], candidates, target);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(0, 0, candidates, target);
        return res;
    }
}

40. 组合总和 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfs(int begin, int sum, int[] candidates, int target) {
        if (sum > target) {
            return;
        } else if (sum == target) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = begin; i < candidates.length; i++) {
            if (i - 1 >= begin && candidates[i] == candidates[i - 1]) {
                continue;
            }
            temp.add(candidates[i]);
            dfs(i + 1, sum + candidates[i], candidates, target);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(0, 0, candidates, target);
        return res;
    }
}

41. 缺失的第一个正数

使用HashSet，将所有的数都存入set中，然后从1开始判断，如果不存在于set中，说明缺失。
时间复杂度On,空间复杂度On，不符合题目空间复杂度O1的要求。

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return nums.length + 1;
    }
}

优化：
把数组本身当做哈希表，把符合条件的数a，放在下标为a-1的位置上。
比如一个数组为[3,1,2] 那么遍历一次之后变成[1,2,3]。
数组的长度为len，遍历数组，只要nums[i]在1 ~ len范围内，且不在正确的位置上（nums[i]-1的位置上），就把它与nums[i] -1位置上的数进行交换。
交换之后还需要循环判断，因为这个交换过来的数，可能也不在正确的位置上，如果不处理它，往后遍历时就把它忽略掉了。
最后再重新遍历一次数组，只要某个位置i上存的数不是i+1，说明是第一个缺失的数。如果都符合，那么缺失的数就是len+1。

class Solution {
    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] >= 1 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                swap(nums, nums[i] - 1, i);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return len + 1;
    }
}

42. 接雨水

使用双指针lo从左往右遍历，hi从右往左遍历。
leftMax记录当前左边最高的柱子，rightMax记录当前右边最高的柱子。
当lo位置的柱子比hi位置的柱子高时，从右往左判断，不断更新rightMax值，只要hi对应的柱子比rightMax小，那么一定可以在hi这根柱子上接到雨水。接到的雨水大小为rightMax-height[hi]。
当lo位置的柱子比hi位置的柱子矮时，从左往右判断，不断更新leftMax值，只要lo对应的柱子比leftMax小，那么一定可以在lo这根柱子上接到雨水。接到的雨水大小为leftMax-height[lo]。

class Solution {
    public int trap(int[] height) {
        int lo = 0, hi = height.length - 1;
        int leftMax = 0, rightMax = 0, res = 0;
        while (lo < hi) {
            if (height[lo] < height[hi]) {
                if (height[lo] < leftMax) {
                    res += leftMax - height[lo];
                } else {
                    leftMax = height[lo];
                }
                lo++;
            } else {
                if (height[hi] < rightMax) {
                    res += rightMax - height[hi];
                } else {
                    rightMax = height[hi];
                }
                hi--;
            }
        }
        return res;
    }
}

45. 跳跃游戏 II

dp[i]代表从第i个位置出发，到达最后一个位置所需的最少步数。

边界：
从最后一个位置出发，只需0步。

转移方程：
从第i个位置出发，如果nums[i]等于0，那么不可能到达最后一个位置，令dp[i]等于-1，代表无法到达。
如果i+nums[i]大于等于最后一个位置，说明一步可以到达,dp[i] 等于1。
其余情况，遍历从i位置出发可以到达的所有位置，只要其中某个位置j的dp值大于等于0，说明从位置i出发也一定可以到达终点，且dp[i] = dp[j] +1。
我们需要找到能到达终点的dp[j]的最小值，再加上1就等于dp[i]。

最后返回dp[0]即可。
时间复杂度On2，空间复杂度On。

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[len - 1] = 0;
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] == 0) {
                dp[i] = -1;//-1说明无法到达
            } else if (i + nums[i] >= nums.length - 1) {
                dp[i] = 1;
            } else {
                int min = Integer.MAX_VALUE;
                for (int j = i + 1; j <= i + nums[i]; j++) {
                    if (dp[j] > 0) {
                        min = Math.min(min, dp[j]);
                    }
                }
                if (min != Integer.MAX_VALUE) {
                    dp[i] = min + 1;
                } else {
                    dp[i] = -1;
                }
            }
        }
        return dp[0];
    }
}

优化：
使用res记录跳跃次数，end记录跳跃次数增加的位置，maxPosition记录当前能到达的最远位置。初始都为0。
遍历数组，不断更新maxPosition，只要当前到达了end位置，就使res加1。
然后end令为maxPosition。
最后一个位置不用遍历，因为到达终点之后就不用跳了。

class Solution {
    public int jump(int[] nums) {
        int end = 0, res = 0, maxPosition = 0;
        for (int i = 0; i < nums.length-1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                res++;
            }
        }
        return res;
    }
}

48. 旋转图像

先进行矩阵的转置，再进行列的翻转。

class Solution {
    public void transpose(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i + 1; j < matrix.length; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

    public void reverseCol(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            int lo = 0, hi = matrix[i].length - 1;
            while (lo < hi) {
                int temp = matrix[i][lo];
                matrix[i][lo] = matrix[i][hi];
                matrix[i][hi] = temp;
                lo++;
                hi--;
            }
        }
    }

    public void rotate(int[][] matrix) {
        transpose(matrix);
        reverseCol(matrix);
    }
}

53. 最大子序和

简单动态规划题。

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int res = nums[0], pre = nums[0];
        for (int i = 1; i < nums.length; i++) {
            pre = Math.max(nums[i], pre + nums[i]);
            res = Math.max(res, pre);
        }
        return res;
    }
}

54. 螺旋矩阵

用LRUD代表左右上下四个边界，不断按螺旋遍历即可。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        int L = 0, R = matrix[0].length - 1, U = 0, D = matrix.length - 1;
        while (true) {
            for (int i = L; i <= R; i++) {
                res.add(matrix[U][i]);
            }
            if (++U > D) {
                break;
            }
            for (int i = U; i <= D; i++) {
                res.add(matrix[i][R]);
            }
            if (--R < L) {
                break;
            }
            for (int i = R; i >= L; i--) {
                res.add(matrix[D][i]);
            }
            if (--D < U) {
                break;
            }
            for (int i = D; i >= U; i--) {
                res.add(matrix[i][L]);
            }
            if (++L > R) {
                break;
            }
        }
        return res;
    }
}