双指针提升有序数组查找效率

题目链接-来源：力扣（LeetCode）

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

思路：

依然使用双指针法。不同的是，本题中我们并没有一个确切的数组大小，我们需要将其考虑为一个「滑动窗口」。由于我们的目标是连续正整数序列，即便我们的数组是虚拟的，我们只需根据前后指针的大小，用等差数列和公式 sum = (a1 + an) * n / 2 （对于本题，即为 sum = (left + right) * (right - left + 1) / 2）即可求出和。

  • 若 sum < target，则我们需扩大窗口，right 右移即可。
  • 若 sum > target，则缩小窗口，left 右移即可
  • 若 sum = target，窗口整体需要右移，由于 left < right，右移结果一定是 sum > target，所以我们直接一步到位，left 右移 2 格，而 right 只右移 1格。
    时间复杂度：O(n)
    空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new LinkedList<>();
        for (int left = 1, right = 2; left < right;) {
            int sum = (left + right) * (right - left + 1) / 2;
            if (sum == target) {
                int[] one = new int[right - left + 1];
                for (int i = 0; i < right - left + 1; i++) {
                    one[i] = left + i;
                }
                res.add(one);
                left += 2;
                right++;
            } else if (sum < target) {
                right++;
            } else {
                left++;
            }
        }
        
        return res.toArray(new int[res.size()][]);
    }
}