LeetCode

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

思路：
数组是有序的，双指针指向数组两端，循环判断二者之和，如果大于目标值则右指针左移，小于目标值则左指针右移。

执行用时：1 ms, 在所有 Java 提交中击败了95.63%的用户。

  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         int len = numbers.length;
  4.         int left = 0, right = len - 1;
  6.         int sum = 0;
  7.         while (left < right) {
  8.             sum = numbers[left] + numbers[right];
  9.             if (sum == target) {
  10.                 return new int[]{left + 1, right + 1};
  11.             } else if (sum > target) {
  12.                 right--;
  13.             } else {
  14.                 left++;
  15.             }
  16.         }
  18.         return new int[]{-1, -1};
  19.     }
  20. }

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

思路：
利用双指针，固定 i，然后移动 left 和 right 来找到 sum 为0的情况。
注意特判和剪枝。特判1，数组长度小于3；特判2，当 i 指向的数大于0，则直接跳出循环，因为数组已排序，后面的数比 i 指向的数要大，不可能满足和为0的情况。剪枝1，i 指向的数和前一个数相等，则直接进入下一次循环；剪枝2，排除 left 和 right 指向重复数字的情况。

执行用时：23 ms, 在所有 Java 提交中击败了82.96%的用户。

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         int len = nums.length;
  5.         if (len < 3) return res; // 特判 1
  7.         Arrays.sort(nums);
  8.         int sum = 0;
  9.         for (int i = 0; i < len - 2; i++) {
  10.             if (nums[i] > 0) break; // 特判 2
  11.             if (i > 0 && nums[i] == nums[i - 1]) continue; // 剪枝 1
  13.             int left = i + 1, right = len - 1;
  14.             while (left < right) {
  15.                 sum = nums[i] + nums[left] + nums[right];
  17.                 if (sum == 0) {
  18.                     res.add(Arrays.asList(nums[i], nums[left], nums[right]));
  20.                     // 剪枝 2
  21.                     while (left < right && nums[left + 1] == nums[left]) {
  22.                         left++;
  23.                     }
  24.                     while (left < right && nums[right - 1] == nums[right]) {
  25.                         right--;
  26.                     }
  28.                     left++;
  29.                     right--;
  30.                 } else if (sum > 0) {
  31.                     right--;
  32.                 } else {
  33.                     left++;
  34.                 }
  35.             }
  36.         }
  37.         return res;
  38.     }
  39. }

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：
双指针（指针对撞）。当左边的最高高度小于右边的最高高度时，最靠左边位置的存水量可以确定。当左边的最高高度大于右边的最高高度时，最靠右边位置的存水量可以确定。每一次 left 和 right 指针向中间移动的过程，都能确定一个位置的存水量。

执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户。

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (len < 3) return 0;

        int left = 0, right = len - 1;
        int curLeftHighest = height[0], curRightHighest = height[len - 1];

        int res = 0;
        while (left < right) {
            curLeftHighest = Math.max(curLeftHighest, height[left]);
            curRightHighest = Math.max(curRightHighest, height[right]);

            if (curLeftHighest < curRightHighest) {
                res += curLeftHighest - height[left];
                left++;
            } else {
                res += curRightHighest - height[right];
                right--;
            }
        }

        return res;
    }
}

练习：

658. 找到 K 个最接近的元素

思路：
双指针+二分法。利用排除法，一个一个删，因为是有序数组，所以从边界删起。在示例中，一共有 7 个元素，要保留 3 个元素，因此要删除 4 个元素。因为要删除的元素都在边界，因此，使用双指针对撞的方式确定保留区间。

16. 最接近的三数之和

思路：
和三数之和类似，将 i 指向的数和左右指针指向的数之和 与 目标值比较。

11. 盛最多水的容器

思路：
比较左右两个指针对应的高度，右边更高则左指针右移，左边更高则右指针左移，同时计算盛水量，保留最大值。

剑指 Offer

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

思路：
双指针。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int[] res = new int[2];
        while (left < right) {
            if ((nums[left] + nums[right]) == target) {
                res[0] = nums[left];
                res[1] = nums[right];
                break;
            } else if ((nums[left] + nums[right]) < target) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

思路：
遍历。（可以用求和公式优化）

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 1; i < target; i++) {
            int temp = 0;
            int j = i;
            while(temp < target) {
                temp += j;
                j++;
            }
            if(temp == target) {//如果找到了那么就要把数据添加到结果数据中。
                List<Integer> newArray = new  ArrayList<>();
                for(int k = i; k < j; k++) {
                    newArray.add(k);
                }
                result.add(newArray);
            }
        }
        int[][] res = new int[result.size()][];
        for (int i = 0; i < result.size(); i++) {
            List<Integer> cur = result.get(i);
            res[i] = new int[cur.size()];
            for (int j = 0; j < cur.size(); j++) {
                res[i][j] = cur.get(j);
            }
        }
        return res;
    }
}

思路2：
滑动窗口。

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1; // 滑动窗口的左边界
        int j = 1; // 滑动窗口的右边界
        int sum = 0; // 滑动窗口中数字的和
        List<int[]> res = new ArrayList<>();

        while (i <= target / 2) {
            if (sum < target) {
                // 右边界向右移动
                sum += j;
                j++;
            } else if (sum > target) {
                // 左边界向右移动
                sum -= i;
                i++;
            } else {
                // 记录结果
                int[] arr = new int[j-i];
                for (int k = i; k < j; k++) {
                    arr[k-i] = k;
                }
                res.add(arr);
                // 左边界向右移动
                sum -= i;
                i++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}