LeetCode18. 四数の和4 Sum JAVA実現
4130 ワード
n個の整数を含む配列numsとターゲット値targetを与え、numsにa+b+c+dの値がtargetと等しいように4つの要素a,b,c,dが存在するかどうかを判断する.条件を満たし、繰り返さないすべての四元グループを見つけます.
注意:
答えに重複する四元グループを含めてはいけません.
例:
配列nums=[1,0,−1,0,−2,2],target=0が与えられる.要求を満たす四元群の集合は,[[−1,0,0,1],[−2,−1,1,2],[−2,0,0,2]]である.
関連参考:LeetCode 16 3 Sum Closest(最も近い3数の和)JAVA実装
leetcode 15三数の和3 Sum JAVA実現
解題構想:二数の和、三数の和、最も近い三数の和を経験した後.四数の和問題を迎え、解題の構想は三数の和と同じである.
配列を並べ替え、四数の和を三数の和に変換し、三数の和を二数の和に変換します.
重さに注意する.
特殊な状況を考慮する:nums.length<4のときCollectionsを呼び出す.EmptyList()は空のリストを返します
78 msかかる
最適化を検討し、
1 ans.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]))を使用して結果リストを装填
2命中していない時は重さを判定しないことができます
3特別な状況を考慮する: nums[i]*4>targetまたはnums[i]+nums[j]*3>targetの場合、現在のループは、より小さな値が見つからないため、継続する必要はありません. nums[i]+nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3]
注意:
答えに重複する四元グループを含めてはいけません.
例:
配列nums=[1,0,−1,0,−2,2],target=0が与えられる.要求を満たす四元群の集合は,[[−1,0,0,1],[−2,−1,1,2],[−2,0,0,2]]である.
関連参考:LeetCode 16 3 Sum Closest(最も近い3数の和)JAVA実装
leetcode 15三数の和3 Sum JAVA実現
解題構想:二数の和、三数の和、最も近い三数の和を経験した後.四数の和問題を迎え、解題の構想は三数の和と同じである.
配列を並べ替え、四数の和を三数の和に変換し、三数の和を二数の和に変換します.
重さに注意する.
特殊な状況を考慮する:nums.length<4のときCollectionsを呼び出す.EmptyList()は空のリストを返します
class Solution {
public List> fourSum(int[] nums, int target) {
if(nums.length < 4 )
return Collections.emptyList();
List> ans = new LinkedList>();
Arrays.sort(nums);
for(int i=0;i0 && nums[i]==nums[i-1])//
continue;
int newTarget = target-nums[i];//
for(int j=i+1;ji+1 && nums[j]==nums[j-1])//
continue;
int newTarget2 = newTarget-nums[j];//
int l = j+1;
int r = nums.length-1;
while(l list = new ArrayList();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[l]);
list.add(nums[r]);
ans.add(list);
while(lr && nums[r]==nums[r-1]) r--;
l++;
r--;
}else if(sum < newTarget2){
while(lr && nums[r]==nums[r-1]) r--;
r--;
}
}
}
}
return ans;
}
}
78 msかかる
最適化を検討し、
1 ans.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]))を使用して結果リストを装填
2命中していない時は重さを判定しないことができます
3特別な状況を考慮する:
class Solution {
public List> fourSum(int[] nums, int target) {
if(nums.length < 4 )
return Collections.emptyList();
List> ans = new LinkedList>();
Arrays.sort(nums);
for(int i=0;i0 && nums[i]==nums[i-1])
continue;
if(nums[i]*4 > target) break;//
if(nums[i]+nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3] < target)
continue;// i
int newTarget = target-nums[i];
for(int j=i+1;ji+1 && nums[j]==nums[j-1])
continue;
if(nums[i]+nums[j]*3 > target)
break;
if(nums[i]+nums[j]+nums[nums.length-1]+nums[nums.length-2] < target)
continue;
int newTarget2 = newTarget-nums[j];
int l = j+1;
int r = nums.length-1;
while(lr && nums[r]==nums[r-1]) r--;
l++;
r--;
}else if(sum < newTarget2){
l++;//
}else{
r--;//
}
}
}
}
return ans;
}
}