今日はケビンのアルゴリズムの旅の21日目です。リートコード問題15を説明するつもりですが、昨日の説明を使って
今回は、3つの数字の和のパズルです。ちょっと難しいかもしれませんので、賢い頭脳を使って、くっついてみてくださいね。
デイリースマイル
私より優れた人たちが努力しないのなら、その人たちは私より優れているのでしょうか？
問題 説明
n 個の整数を含む配列 nums が与えられたとき、a + b + c = 0 となるような 3 つの要素 a, b, c が nums に存在するかどうかを判定しなさい。条件を満たし、重複しない3つの要素をすべて求めなさい。
注：回答には重複したトリプルを含めないでください。
例
nums = [-1, 0, 1, 2, -1, -4] という配列が与えられます。
要件を満たすトリプルの集合は次のとおりです： [ [-1, 0, 1], [-1, -1, 2] ]。
問題解決
ダブルポインター
この問題のアルゴリズムの考え方は以下の通り：
- 特殊な判定として、配列の長さがnの場合、配列がnullか配列の長さが3未満の場合は[]をそのまま返します。
- 配列をソートします。
- ソートされた配列を繰り返します：
- nums[i]>0の場合：すでにソートされているので、その後に0を足す数字が3つ続くことはありません。
- 要素が重複している場合：重複解を避けるためにスキップします。
- 左ポインタL = i + 1、右ポインタR = n - 1となるようにします。
- nums[i]+nums[L]+nums[R]==0のとき、結果集合に要素を追加する要件を満たし、ループを実行し、次の位置で左境界と右境界が重複しているかどうかを判断し、重複解を削除します。同時にL,Rを次の位置に移動して新しい解を求めます。
- 和が0より大きい場合は、nums[R]が大きすぎるので、Rを左に移動します。
- 和が 0 より小さい場合は、nums[L] が小さすぎるので、L を右に移動します。
コードの実装
//go
func threeSum(nums []int) [][]int {
var result [][]int // 結果を記録する
length := len(nums) // 配列の長さを求める
if nums == nil || length < 3 {
return result
}
sort.Ints(nums) //
for i := 0; i < length; i++ {
// 現在の数字が0より大きい場合、3つの数字の和は0より大きくなければならないので、ループを終了する。
if nums[i] > 0 {
break
}
// 重複排除、添え字iの数
if i > 0 && nums[i] == nums[i-1] {
continue
}
l := i + 1
r := length - 1
for {
if l >= r {
break
}
sum := nums[i] + nums[l] + nums[r]
if sum > 0 {
r --
continue
}
if sum < 0 {
l ++
continue
}
if sum == 0 {
result = append(result, []int{nums[i], nums[l], nums[r]})
// 重みをなくす、添え字をつける l
for l < r && nums[l] == nums[l+1] {
l++
}
// 重複排除、添え字r
for l < r && nums[r] == nums[r-1] {
r--
}
l++
r--
}
}
}
return result
}
//java
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); //
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 現在の数字が0より大きい場合、3つの数字の和は0より大きくなければならないので、ループを終了する。
if(i > 0 && nums[i] == nums[i-1]) continue; //
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L<R && nums[L] == nums[L+1]) L++; //
while (L<R && nums[R] == nums[R-1]) R--; //
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
}
念のため：
ここに示されたコードはLeetCodeを通して実行されました！
チャッターボックスにて
多くの人が良い習慣を身につけたいと願っていますが、ほとんどの人は3分間人間です。そのため、次のような計画を立てることにしました。
一緒にアルゴリズムを学び、ボーナスを受け取ってください！
参加様式：
また、多くの友人と「会う」こともできます。
団結し、共に学び、共に向上すること！
パンチカードのルールは
報酬
連続出勤1日につき $6.60の レッドパケットを私にご連絡ください！
連続出勤1日ごとに $16.60の レッドパケットをお渡しします！
66.60ドルの レッドパケットをご希望の方はご連絡ください！
個人的なエネルギーは十分ではありませんが、コンテンツは主に公開プラットフォームで公開され、他のプラットフォームは、タイムリーに更新されない場合があり、私は〜を許して願っています！
