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()は空のリストを返します
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特別な状況を考慮する:
  • nums[i]*4>targetまたはnums[i]+nums[j]*3>targetの場合、現在のループは、より小さな値が見つからないため、継続する必要はありません.
  • nums[i]+nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-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;
        }
    }