* 数之和

两数之和

先贴出题目

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

哈希表法

这题因为题目已经说了有一种答案,所以不用担心 [3],6 这种情况,哪怕有重复元素,也会被最新的覆盖

两数之和没法用双指针,因为返回的数组存储的是索引,没法排序

class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if(nums == null || nums.length == 0){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i]; // 遍历当前元素,并在map中寻找是否有匹配的key
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);
break;
}
map.put(nums[i], i); // 如果没找到匹配对,就把访问过的元素和下标加入到map中
}
return res;
}
}

三数之和

先贴出题目

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

双指针法

这题第一想法可能会想到双指针,但我太笨了,想到的是左右指针在两边,并和两者之间的元素匹配,这样去重非常麻烦,而且,我没做出来。这题看了卡哥的题解,从左向右遍历,左指针在当前元素右边,右指针从右往左走,这样去重逻辑会清晰很多。

注意三个元素都要去重,假设三个元素按序分别为a b c

对 a 去重注意逻辑:

一开始写成

if(nums[i] == nums[i + 1]){
continue;
}

这样出现一个明显的问题,比如 [-1,-1,2] 这个解直接跳过了

所以,应该和前一个比较

if(i > 0 && nums[i] == nums[i - 1]){ // 对第一个数去重
continue;
}

这样,先记录了解再跳过,就不会漏答案

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for(int i = 0;i < nums.length;i++){
if(nums[i] > 0){ // 排序后第一个数就大于0那么和不可能为0
return result;
}
if(i > 0 && nums[i] == nums[i - 1]){ // 对第一个数去重
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(right > left){
int curSum = nums[i] + nums[left] + nums[right];
if(curSum > 0){
right--;
}else if(curSum < 0){
left++;
}else{
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
// 对b、c去重
while(right > left && nums[right] == nums[right - 1]) right--;
while(right > left && nums[left] == nums[left + 1]) left++;

//左右指针同时收缩
left++;
right--;
}
}
}
return result;
}
}

四数之和

直接给出代码吧,可以对比三数之和,很明显能看出来就是多了一层for循环

class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i < nums.length;i++){
if(nums[i] > 0 && nums[i] > target) return result;
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1;j < nums.length;j++){
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.length - 1;
while(right > left){
long curSum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if(curSum > target){
right--;
}else if(curSum < target){
left++;
}else{
result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while(right > left && nums[right] == nums[right - 1]) right--;
while(right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return result;
}
}

可以提出一些公共部分

排序,这一步是必须的,不然没法去重

首先,对第一个数去重,这两步很关键

if(nums[i] > 0 && nums[i] > target){
return result;
}
if(i > 0 && nums[i - 1] == nums[i]){
continue;
}

然后,找到左指针和右指针(相对而言的)

int left = i + 1;
int right = nums.length - 1;

对左右指针去重

while(right > left && nums[left] == nums[left + 1]) left++;
while(right > left && nums[right] == nums[right - 1]) right--;
// 去重之后,记得同时缩减,因为当前记录已经记下来了
right--;
left++;

当你将这些步骤理解清楚,多数之和问题就能迎刃而解了