LetCode 15三数の和


ヒント
LintCodeの関連アルゴリズムの問題の実装コードは、私のGithHubでダウンロードすることができます.
テーマの要件
n個の整数を含む配列numsが与えられ、a+b+c=0となるように、numsに3つの要素a,b,cが存在するか否かが判断される.条件を満たし、繰り返さないすべての三元グループを見つけます.
注意:答えに重複する三元グループは含まれてはいけません.
  ,      nums = [-1, 0, 1, 2, -1, -4],

           :
[
  [-1, 0, 1],
  [-1, -1, 2]
]

問題を解く構想.
最初はとても簡単に考えて、3つの遍歴をして、条件を満たすものを1つのリストに入れて、それからこのリストを既存の条件を満たすリストと比較して、要素が同じかどうかを見て、ある場合は参加しません.
3つのサイクルが時間がかかりすぎて、時間が複雑で、現在条件を満たしている集合を比較すると、より時間がかかるため、タイムアウトするのは明らかです.
まず、元の配列を小さいものから大きいものに並べ替え、2つの要素iとjを固定し、iを後ろに、jを後ろに、iを後ろに、jを配列の末尾の下付き文字にリセットし、iとjの間にnums[i]+nums[j]+nums[k]=0を成立させるkを探すことができます.
では、どうやって重くしますか?
毎回nums[i]+nums[j]+nums[k]==0が成立したi,j,kが得られた後、nums[i]!=nums[i+1]は、nums[j]!=までjを前進させる.nums[j - 1].これにより、得られた3つの数字が重複しないことが保証されます.次はコードです
インプリメンテーションコード
class Solution {
    public List> threeSum(int[] nums) {
        List> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = nums.length - 1;
            int target = 0 - nums[i];
            int k = i + 1;
            while (k < j) {
                if (nums[k] + nums[j] == target) {
                    List item = Arrays.asList(nums[i], nums[k], nums[j]);
                    result.add(item);
                    while (k < j && nums[k] == nums[k + 1]) k++;
                    while (k < j && nums[j] == nums[j - 1]) j--;
                    k++;j--;
                } else if (nums[k] + nums[j] < target) {
                    k++;
                } else {
                    j--;
                }
            }
        }
        return result;
    }
}