在开始时同时初始化指针与在开始时初始化指针和在结束时初始化另一个指针背后的直觉
Intuition behind initializing both the pointers at the beginning versus one at the beginning and other at the ending
我前几天解决了一个问题：
Given an unsorted array A containing N integers and an integer B, find if there exists a pair of elements in the array whose difference is B. Return true if any such pair exists else return false. For [2, 3, 5, 10, 50, 80]; B=40;, it should return true.
为：
int Solution::solve(vector<int> &A, int B) {
if(A.size()==1) return false;
int i=0, j=0; //note: both initialized at the beginning
sort(begin(A), end(A));
while(i< A.size() && j<A.size()) {
if(A[j]-A[i]==B && i!=j) return true;
if(A[j]-A[i]<B) j++;
else i++;
}
return false;
}
在解决这个问题时，我之前犯的 错误 是初始化 i=0 和 j=A.size()-1。因此，递减 j 和递增 i 两者 都减少了差异，因此错过了有效差异。像上面一样一开始就初始化，问题就解决了。
现在我正在解决一个后续的3sum问题：
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. If nums = [-1,0,1,2,-1,-4], output should be: [[-1,-1,2],[-1,0,1]] (any order works).
此问题的 solution 给出为：
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (unsigned int i=0; i<nums.size(); i++) {
if ((i>0) && (nums[i]==nums[i-1]))
continue;
int l = i+1, r = nums.size()-1; //note: unlike `l`, `r` points to the end
while (l<r) {
int s = nums[i]+nums[l]+nums[r];
if (s>0) r--;
else if (s<0) l++;
else {
res.push_back(vector<int> {nums[i], nums[l], nums[r]});
while (nums[l]==nums[l+1]) l++;
while (nums[r]==nums[r-1]) r--;
l++; r--;
}
}
}
return res;
}
逻辑非常简单：每个 nums[i]s（来自外部循环）是我们搜索的 'target'，在内部 while 循环中使用双指针方法，如第一个代码在顶部。
我没有遵循的是初始化 r=nums.size()-1 和向后工作背后的逻辑 - 如何不遗漏有效差异（在本例中，实际上是“总和”）？
Edit1：两个问题都包含负数和正数，以及零。
Edit2：我了解这两个片段的工作原理。我的问题具体是代码#2中r=nums.size()-1背后的原因：正如我们在上面的代码#1中看到的那样，从末尾开始r会错过一些有效的对（http://cpp.sh/36y27 - 有效对 (10,50) 是 missed）；那么为什么我们不会错过第二个代码中的有效对？
重新表述问题
两种算法之间的区别归结为加法和减法，而不是 3 对 2 和。
您的 3-sum 变体要求匹配目标的 3 个数字的总和。当您在外循环中修复一个数字时，内循环将减少为 2-sum，即 实际上是 2-sum（即加法）。顶部代码中的“2-sum”变体实际上是 2-difference（即减法）。
您正在将 2 和 (A[i] + A[j] == B s.t. i != j) 与 2 差 (A[i] - A[j] == B s.t. i != j).我将继续使用这些术语，而忘记 3-sum 中的外循环作为红鲱鱼。
2-sum
为什么 L = 0, R = length - 1 适用于 2-sum
对于 2-sum，您可能已经看到从末端开始向中间工作的直觉，但值得将逻辑明确化。
在循环中的任何一次迭代中，如果总和为A[L] + A[R] > B，那么我们别无选择，只能将右指针递减到较低的索引。增加左指针肯定会增加我们的总和或保持不变，我们将离目标越来越远，可能会关闭找到解决方案对的可能性，这很可能仍然包括 A[L]。
另一方面，如果 A[L] + A[R] < B，则您必须通过将左指针向前移动到更大的数字来增加总和。有可能 A[R] 仍然是总和的一部分——我们不能保证它不是总和的一部分，直到 A[L] + A[R] > B.
关键要点是每个步骤无需做出决定：要么找到答案，要么可以明确地从任一索引处的两个数字中删除一个进一步考虑。
为什么 L = 0, R = 0 不适用于 2-sum
这解释了为什么两个数字都从 0 开始对 2 和没有帮助。您将使用什么规则来增加指针以找到解决方案？没有办法知道哪个指针需要前进，哪个应该等待。两种移动最多都会增加和，而不会减少和（开始是最小和，A[0] + A[0]）。移动错误的数字可能会阻碍以后找到解决方案，并且没有办法明确消除任何一个数字。
您又回到了将左指针保持在 0 并将右指针向前移动到导致 A[R] + A[L] > B 的第一个元素，然后 运行 久经考验的原始两指针逻辑。您不妨从 R 开始 length - 1。
2 差
为什么 L = 0, R = length - 1 不适用于 2 差
现在我们了解了 2-sum 的工作原理，让我们看看 2-difference。为什么同样的方法从两头开始，向中间努力却行不通？
原因是，当您减去两个数字时，您失去了 2-sum 的最重要保证，即向前移动左指针将始终增加总和，而向后移动右指针将始终减少总和.
在排序数组中的两个数字之间进行减法，A[R] - A[L] s.t。 R > L，无论你向前移动L还是向后移动R，总和都会减少，即使是在一个只有正数的数组中。这意味着在给定的索引处，没有办法知道以后需要移动哪个指针才能找到正确的对，由于与 2-sum 相同的原因破坏了算法，两个指针都从 0 开始。
为什么 L = 0, R = 0 适用于 2 差分
最后，为什么两个指针都从 0 开始对 2-difference 起作用？原因是您回到了 2-sum 保证，即移动一个指针会增加差异而另一个会减少差异。具体来说，如果 A[R] - A[L] < B，则 L++ 保证减小差异，而 R++ 保证增加差异。
我们回来了：没有选择或神奇的神谕来决定移动哪个索引。我们可以系统地消除太大或太小的值，并专注于目标。该逻辑的工作原理与 L = 0, R = length - 1 适用于 2-sum 的原因相同。
顺便说一句，第一个解决方案是次优的 O(n log(n)) 而不是 O(n) 两次通过和 O(n) space。您可以使用无序地图来跟踪到目前为止看到的项目，然后对数组中的每个项目执行查找：如果 B - A[i] for some i 在地图中，则您找到了您的一对。
考虑一下：
A = {2, 3, 5, 10, 50, 80}
B = 40
i = 0, j = 5;
当你有类似的东西时
while(i<j) {
if(A[j]-A[i]==B && i!=j) return true;
if(A[j]-A[i]>B) j--;
else i++;
}
考虑 if(A[j]-A[i]==B && i!=j) 不正确 的情况。您的代码做出了一个错误的假设，即如果两个端点的差异为 > B，则应该递减 j。给定一个排序数组，您不知道是递减 j 然后取差会得到目标差，还是递增 i 然后取差会得到目标数，因为它可以双向。在您的示例中，当 A[5] - A[0] != 10 您可以双向选择时，A[4] - A[0]（这就是您所做的）或 A[5] - A[1]。两者都会 still 给你一个大于目标差异的差异。简而言之，您算法中的假设是不正确的，因此不是正确的方法。
在第二种方法中，情况并非如此。当找不到三元组 nums[i]+nums[l]+nums[r] 时，您知道数组已排序，如果总和大于 0，则必须意味着 num[r] 需要递减，因为递增 l 只会进一步增加总和，因为 num[l + 1] > num[l].
您的问题归结为以下几点：
对于按升序排序的数组 A，为什么我们对 t 执行不同的两指针搜索以解决问题 A[i] + A[j] == t 与 A[i] - A[j] == t , 其中 j > i?
更直观的是为什么第一个问题，我们可以固定i和j在两端，减少j或增加i，所以我会专注于第二个问题。
对于数组问题，有时最容易得出解决方案 space，然后从中得出算法。首先，让我们得出解决方案 space B，其中 B[i][j] = -(A[i] - A[j])（仅针对 j > i 定义）：
B, for A of length N
i ---------------------------->
j B[0][0] B[0][1] ... B[0][N - 1]
| B[1][0] B[1][1] ... B[1][N - 1]
| . . .
| . . .
| . . .
v B[N - 1][0] B[N - 1][1] ... B[N - 1][N - 1]
---
In terms of A:
X -(A[0] - A[1]) -(A[0] - A[2]) ... -(A[0] - A[N - 2]) -(A[0] - A[N - 1])
X X -(A[1] - A[2]) ... -(A[1] - A[N - 2]) -(A[1] - A[N - 1])
. . . . .
. . . . .
. . . . .
X X X ... X -(A[N - 2] - A[N - 1])
X X X ... X X
注意B[i][j] = A[j] - A[i]，所以B的行是升序，B的列是降序命令。让我们为 A = [2, 3, 5, 10, 50, 80].
计算 B
B = [
i------------------------>
j X 1 3 8 48 78
| X X 2 7 47 77
| X X X 5 45 75
| X X X X 40 70
| X X X X X 30
v X X X X X X
]
现在等效的问题是在 B 中搜索 t = 40。请注意，如果我们从 i = 0 和 j = N = 5 开始，则没有 good/guaranteed 到达 [=29] 的方法=].但是，如果我们从始终可以 increment/decrement 小步 B 当前元素的位置开始，我们可以保证我们将尽可能接近 t。
在这种情况下，我们采取的小步骤涉及遍历矩阵中的 right/downwards，从左上角开始（相当于从右下角遍历 left/upwards），对应于 递增 i 和 j 在 A.
的原始问题中
我前几天解决了一个问题：
Given an unsorted array
AcontainingNintegers and an integerB, find if there exists a pair of elements in the array whose difference isB. Returntrueif any such pair exists else returnfalse. For[2, 3, 5, 10, 50, 80]; B=40;, it should returntrue.
为：
int Solution::solve(vector<int> &A, int B) {
if(A.size()==1) return false;
int i=0, j=0; //note: both initialized at the beginning
sort(begin(A), end(A));
while(i< A.size() && j<A.size()) {
if(A[j]-A[i]==B && i!=j) return true;
if(A[j]-A[i]<B) j++;
else i++;
}
return false;
}
在解决这个问题时，我之前犯的 错误 是初始化 i=0 和 j=A.size()-1。因此，递减 j 和递增 i 两者 都减少了差异，因此错过了有效差异。像上面一样一开始就初始化，问题就解决了。
现在我正在解决一个后续的3sum问题：
Given an integer array
nums, return all the triplets[nums[i], nums[j], nums[k]]such thati != j,i != k, andj != k, andnums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Ifnums = [-1,0,1,2,-1,-4], output should be:[[-1,-1,2],[-1,0,1]](any order works).
此问题的 solution 给出为：
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (unsigned int i=0; i<nums.size(); i++) {
if ((i>0) && (nums[i]==nums[i-1]))
continue;
int l = i+1, r = nums.size()-1; //note: unlike `l`, `r` points to the end
while (l<r) {
int s = nums[i]+nums[l]+nums[r];
if (s>0) r--;
else if (s<0) l++;
else {
res.push_back(vector<int> {nums[i], nums[l], nums[r]});
while (nums[l]==nums[l+1]) l++;
while (nums[r]==nums[r-1]) r--;
l++; r--;
}
}
}
return res;
}
逻辑非常简单：每个 nums[i]s（来自外部循环）是我们搜索的 'target'，在内部 while 循环中使用双指针方法，如第一个代码在顶部。
我没有遵循的是初始化 r=nums.size()-1 和向后工作背后的逻辑 - 如何不遗漏有效差异（在本例中，实际上是“总和”）？
Edit1：两个问题都包含负数和正数，以及零。
Edit2：我了解这两个片段的工作原理。我的问题具体是代码#2中r=nums.size()-1背后的原因：正如我们在上面的代码#1中看到的那样，从末尾开始r会错过一些有效的对（http://cpp.sh/36y27 - 有效对 (10,50) 是 missed）；那么为什么我们不会错过第二个代码中的有效对？
重新表述问题
两种算法之间的区别归结为加法和减法，而不是 3 对 2 和。
您的 3-sum 变体要求匹配目标的 3 个数字的总和。当您在外循环中修复一个数字时，内循环将减少为 2-sum，即 实际上是 2-sum（即加法）。顶部代码中的“2-sum”变体实际上是 2-difference（即减法）。
您正在将 2 和 (A[i] + A[j] == B s.t. i != j) 与 2 差 (A[i] - A[j] == B s.t. i != j).我将继续使用这些术语，而忘记 3-sum 中的外循环作为红鲱鱼。
2-sum
为什么 L = 0, R = length - 1 适用于 2-sum
对于 2-sum，您可能已经看到从末端开始向中间工作的直觉，但值得将逻辑明确化。
在循环中的任何一次迭代中，如果总和为A[L] + A[R] > B，那么我们别无选择，只能将右指针递减到较低的索引。增加左指针肯定会增加我们的总和或保持不变，我们将离目标越来越远，可能会关闭找到解决方案对的可能性，这很可能仍然包括 A[L]。
另一方面，如果 A[L] + A[R] < B，则您必须通过将左指针向前移动到更大的数字来增加总和。有可能 A[R] 仍然是总和的一部分——我们不能保证它不是总和的一部分，直到 A[L] + A[R] > B.
关键要点是每个步骤无需做出决定：要么找到答案，要么可以明确地从任一索引处的两个数字中删除一个进一步考虑。
为什么 L = 0, R = 0 不适用于 2-sum
这解释了为什么两个数字都从 0 开始对 2 和没有帮助。您将使用什么规则来增加指针以找到解决方案？没有办法知道哪个指针需要前进，哪个应该等待。两种移动最多都会增加和，而不会减少和（开始是最小和，A[0] + A[0]）。移动错误的数字可能会阻碍以后找到解决方案，并且没有办法明确消除任何一个数字。
您又回到了将左指针保持在 0 并将右指针向前移动到导致 A[R] + A[L] > B 的第一个元素，然后 运行 久经考验的原始两指针逻辑。您不妨从 R 开始 length - 1。
2 差
为什么 L = 0, R = length - 1 不适用于 2 差
现在我们了解了 2-sum 的工作原理，让我们看看 2-difference。为什么同样的方法从两头开始，向中间努力却行不通？
原因是，当您减去两个数字时，您失去了 2-sum 的最重要保证，即向前移动左指针将始终增加总和，而向后移动右指针将始终减少总和.
在排序数组中的两个数字之间进行减法，A[R] - A[L] s.t。 R > L，无论你向前移动L还是向后移动R，总和都会减少，即使是在一个只有正数的数组中。这意味着在给定的索引处，没有办法知道以后需要移动哪个指针才能找到正确的对，由于与 2-sum 相同的原因破坏了算法，两个指针都从 0 开始。
为什么 L = 0, R = 0 适用于 2 差分
最后，为什么两个指针都从 0 开始对 2-difference 起作用？原因是您回到了 2-sum 保证，即移动一个指针会增加差异而另一个会减少差异。具体来说，如果 A[R] - A[L] < B，则 L++ 保证减小差异，而 R++ 保证增加差异。
我们回来了：没有选择或神奇的神谕来决定移动哪个索引。我们可以系统地消除太大或太小的值，并专注于目标。该逻辑的工作原理与 L = 0, R = length - 1 适用于 2-sum 的原因相同。
顺便说一句，第一个解决方案是次优的 O(n log(n)) 而不是 O(n) 两次通过和 O(n) space。您可以使用无序地图来跟踪到目前为止看到的项目，然后对数组中的每个项目执行查找：如果 B - A[i] for some i 在地图中，则您找到了您的一对。
考虑一下：
A = {2, 3, 5, 10, 50, 80}
B = 40
i = 0, j = 5;
当你有类似的东西时
while(i<j) {
if(A[j]-A[i]==B && i!=j) return true;
if(A[j]-A[i]>B) j--;
else i++;
}
考虑 if(A[j]-A[i]==B && i!=j) 不正确 的情况。您的代码做出了一个错误的假设，即如果两个端点的差异为 > B，则应该递减 j。给定一个排序数组，您不知道是递减 j 然后取差会得到目标差，还是递增 i 然后取差会得到目标数，因为它可以双向。在您的示例中，当 A[5] - A[0] != 10 您可以双向选择时，A[4] - A[0]（这就是您所做的）或 A[5] - A[1]。两者都会 still 给你一个大于目标差异的差异。简而言之，您算法中的假设是不正确的，因此不是正确的方法。
在第二种方法中，情况并非如此。当找不到三元组 nums[i]+nums[l]+nums[r] 时，您知道数组已排序，如果总和大于 0，则必须意味着 num[r] 需要递减，因为递增 l 只会进一步增加总和，因为 num[l + 1] > num[l].
您的问题归结为以下几点：
对于按升序排序的数组 A，为什么我们对 t 执行不同的两指针搜索以解决问题 A[i] + A[j] == t 与 A[i] - A[j] == t , 其中 j > i?
更直观的是为什么第一个问题，我们可以固定i和j在两端，减少j或增加i，所以我会专注于第二个问题。
对于数组问题，有时最容易得出解决方案 space，然后从中得出算法。首先，让我们得出解决方案 space B，其中 B[i][j] = -(A[i] - A[j])（仅针对 j > i 定义）：
B, for A of length N
i ---------------------------->
j B[0][0] B[0][1] ... B[0][N - 1]
| B[1][0] B[1][1] ... B[1][N - 1]
| . . .
| . . .
| . . .
v B[N - 1][0] B[N - 1][1] ... B[N - 1][N - 1]
---
In terms of A:
X -(A[0] - A[1]) -(A[0] - A[2]) ... -(A[0] - A[N - 2]) -(A[0] - A[N - 1])
X X -(A[1] - A[2]) ... -(A[1] - A[N - 2]) -(A[1] - A[N - 1])
. . . . .
. . . . .
. . . . .
X X X ... X -(A[N - 2] - A[N - 1])
X X X ... X X
注意B[i][j] = A[j] - A[i]，所以B的行是升序，B的列是降序命令。让我们为 A = [2, 3, 5, 10, 50, 80].
B
B = [
i------------------------>
j X 1 3 8 48 78
| X X 2 7 47 77
| X X X 5 45 75
| X X X X 40 70
| X X X X X 30
v X X X X X X
]
现在等效的问题是在 B 中搜索 t = 40。请注意，如果我们从 i = 0 和 j = N = 5 开始，则没有 good/guaranteed 到达 [=29] 的方法=].但是，如果我们从始终可以 increment/decrement 小步 B 当前元素的位置开始，我们可以保证我们将尽可能接近 t。
在这种情况下，我们采取的小步骤涉及遍历矩阵中的 right/downwards，从左上角开始（相当于从右下角遍历 left/upwards），对应于 递增 i 和 j 在 A.