Leetcode 454
題目鏈接：四數(shù)相加 II
題目分了四個數(shù)組，每個里面取一個數(shù)卦羡，不需要考慮去重的問題噪馏，相對簡單，將四個數(shù)組兩兩分組：
- 把前兩個數(shù)組求和的每一種可能都加入
HashMap中（key是和绿饵，value是出現(xiàn)的個數(shù)） - 對后兩個數(shù)組每一次求和后欠肾，檢查
HashMap中是否存在和為0的數(shù)，若有則結(jié)果加上該數(shù)次數(shù)
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int n = nums1.length;
int result=0;
HashMap<Integer,Integer> hashmap = new HashMap<>();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
hashmap.put(-nums1[i]-nums2[j], hashmap.getOrDefault(-nums1[i]-nums2[j], 0)+1);
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(hashmap.containsKey(nums3[i] + nums4[j])){
result += hashmap.getOrDefault(nums3[i] + nums4[j], 0);
}
}
}
return result;
}
LeetCode 15
題目鏈接：三數(shù)之和
在一個數(shù)組里面找出所有不重復(fù)的三個元素拟赊，滿足和為target
采用雙指針法：
- 首先對數(shù)組進(jìn)行排序
- 第一個for循環(huán)固定遍歷第一個元素
- 第二個循環(huán)移動兩個指針的位置刺桃，移動邏輯為
if(nums[right]+nums[left]==target){
//找到的答案
}
//需要縮小和，只能移動right
if(nums[right]+nums[left]>target){
right--;
}
//需要增大和吸祟，只能移動left
if(nums[right]+nums[left]<target){
left++;
}
- 考慮去重復(fù)：最外層的一次遍歷結(jié)束后瑟慈，如果下一個要遍歷的元素值相等，則跳過這一層遍歷屋匕，因為上一次遍歷已經(jīng)把這個元素值為第一個值的所有情況全部遍歷了葛碧；同理其他的也是
整體代碼如下
public List<List<Integer>> threeSum(int[] nums) {
//一切的基礎(chǔ)，雙指針法要求必須排序
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for(int i=0;i<nums.length-2;i++){
//對于第一個元素的去重
if(i>0&&nums[i-1]==nums[i]) continue;
int target = -nums[i];
int left = i+1;
int right = nums.length-1;
while(left<right){
if(nums[right]+nums[left]==target){
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
//left去重
while(left<right&&nums[left]==nums[left-1]){
left++;
}
//right去重
while(left<right&&nums[right]==nums[right+1]){
right--;
}
}
//雙指針移動的規(guī)則體現(xiàn)
if(nums[right]+nums[left]>target){
right--;
}
if(nums[right]+nums[left]<target){
left++;
}
}
}
return result;
}
LeetCode 18
題目鏈接：四數(shù)之和
升級版三數(shù)之和过吻，還是使用雙指針进泼，循環(huán)再加一層
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for(int i=0; i<nums.length-3;i++){
if(i>0&&nums[i]==nums[i-1])
continue;
for(int j=nums.length-1;j>=i+3;j--){
if(j<nums.length-1&&nums[j]==nums[j+1])
continue;
int left = i+1;
int right = j-1;
while(left<right){
if((long)nums[i]+nums[j]+nums[left]+nums[right]==target){
List<Integer> list = new ArrayList<>();
Collections.addAll(list, nums[i],nums[j],nums[left],nums[right]);
result.add(list);
left++;
right--;
while(nums[left]==nums[left-1]&&left<right){
left++;
}
while(nums[right]==nums[right+1]&&left<right){
right--;
}
}
if((long)nums[i]+nums[j]+nums[left]+nums[right]>target){
right--;
}
if((long)nums[i]+nums[j]+nums[left]+nums[right]<target){
left++;
}
}
}
}
return result;
}
