双指针对撞，首先要先排序。
LeetCode 第 15 题：3Sum
传送门：英文网址：15. 3Sum ，中文网址：15. 三数之和 。
给定一个包含 n 个整数的数组
nums，判断nums中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
思路：“排序” + “指针对撞”。首先固定 ，然后在剩下的数组中找
。
注意点 1：首先要排序；
注意点 2：在排序的过程中，要去重。下面这行代码的意思就是：只要和前面一个一样的，我这一轮就跳过了。
if i > 0 and nums[i] == nums[i - 1]:
continue
注意点 3：找到了一个解以后，继续去重。
# 注意：这一步在去重，是第一种解法 set 做不到的
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
注意点 4：如果开头那个数字就大于 了，就没有必要循环下去了。
Python 代码1：
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
# 用指针对撞的方式
l = i + 1
r = len(nums) - 1
# 不能等于，等于就变成取一样的数了
while l < r:
s = nums[i] + nums[l] + nums[r]
if s > 0:
r -= 1
elif s < 0:
l += 1
else:
res.append([nums[i], nums[l], nums[r]])
# 注意：这一步在去重，是第一种解法 set 做不到的
# 看一看右边是不是和自己相等，如果相等，就向右边移动一格
while l < r and nums[l] == nums[l + 1]:
l += 1
# 看一看左边是不是和自己相等，如果相等，就向右边移动一格
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return res
思路2：借助 LeetCode 第 1 题：两数之和 的思路，每一轮使用一个新的哈希表用于去重。
Python 代码2：
class Solution(object):
# 排序可以去掉 -4 但是不能把后面重复的 2 去掉
# [-4,-4,2,2]
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3:
return []
nums.sort()
# 特判
if nums[0] == nums[-1] == 0:
return [[0, 0, 0]]
res = set()
# 最后两个数就没有必要作为遍历的起点了
for index, one in enumerate(nums[:-2]):
# 因为题目要求，答案中不可以包含重复的三元组。
if index >= 1 and nums[index] == nums[index - 1]:
continue
s = set()
for two in nums[index + 1:]:
if two not in s:
s.add(-one - two)
else:
# 找到了一个解
res.add((one, two, -one - two))
return list(map(list, res))
总结：两种方法都要排序，因为题目中说了，要不重复。
LeetCode 第 18 题：4Sum
传送门：英文网址：18. 4Sum ，中文网址：18. 四数之和 。
给定一个包含 n 个整数的数组
nums和一个目标值target，判断nums中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与target相等？找出所有满足条件且不重复的四元组。注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
分析：采用了“三数之和”的解法，在外面多套了一层。
Java 代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
// time : O(n^3);
// space : O(n);
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
if (len < 4) {
return res;
}
Arrays.sort(nums);
// len-4 len-3 len-2 len-1
for (int i = 0; i < len - 3; i++) {
// 跳过重复的解 1（以排序为前提）
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// len-3 len-2 len-1
for (int j = i + 1; j < len - 2; j++) {
// 跳过重复的解 2（以排序为前提）
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 接下来使用指针对撞
int left = j + 1;
int right = len - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
List<Integer> oneSolution = new ArrayList<>();
oneSolution.add(nums[i]);
oneSolution.add(nums[j]);
oneSolution.add(nums[left]);
oneSolution.add(nums[right]);
res.add(oneSolution);
// 跳过重复的解 3（以排序为前提）
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
// 这一步不要忘记了
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
List<List<Integer>> fourSum = solution.fourSum(nums, target);
System.out.println(fourSum);
}
}
小 Fu 的解法：事实上只是比“三数之和”多了一个循环。
image-20190127112007218
LeetCode 第 16 题：3Sum Closest
传送门：英文网址：16. 3Sum Closest ，中文网址：16. 最接近的三数之和 。
给定一个包括 n 个整数的数组
nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
分析：求最接近的三数之和。和二分查找没有什么关系，就是双指针对撞。因为题目要求不能出现重复答案，因此首先还是要排序。
Python 代码：
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) < 3:
return []
# 初始化
diff = float('inf')
nums.sort()
for index in range(len(nums) - 2):
if index > 0 and nums[index] == nums[index - 1]:
continue
l = index + 1
r = len(nums) - 1
while l < r:
s = nums[index] + nums[l] + nums[r]
if abs(s - target) < diff:
diff = abs(s - target)
res = s
if s > target:
r -= 1
elif s < target:
l += 1
else:
# 如果已经等于 target 的话, 肯定是最接近的，根据题目要求，返回这三个数的和
return target
return res
（本节完）
网友评论