LetCode 15三数の和
1899 ワード
ヒント
LintCodeの関連アルゴリズムの問題の実装コードは、私のGithHubでダウンロードすることができます.
テーマの要件
n個の整数を含む配列
注意:答えに重複する三元グループは含まれてはいけません.
問題を解く構想.
最初はとても簡単に考えて、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つの数字が重複しないことが保証されます.次はコードです
インプリメンテーションコード
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;
}
}