Java [leetcode 15] 3Sum
1808 ワード
問題の説明:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets.
問題を解く構想.
このような無秩序配列については,まず昇順配列を行い,非減算配列にするためにjavaが持つArrays.sort()メソッドを呼び出せばよい.
次に最小の数を固定するたびに、後ろの配列から他の2つの数の和がその数の反対の数であることを見つければよい.
具体的な手順はブログを参照してください.http://blog.csdn.net/zhouworld16/article/details/16917071
コード実装:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
問題を解く構想.
このような無秩序配列については,まず昇順配列を行い,非減算配列にするためにjavaが持つArrays.sort()メソッドを呼び出せばよい.
次に最小の数を固定するたびに、後ろの配列から他の2つの数の和がその数の反対の数であることを見つければよい.
具体的な手順はブログを参照してください.http://blog.csdn.net/zhouworld16/article/details/16917071
コード実装:
public class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> threeSum(int[] nums) {
int length = nums.length;
if (nums == null || length < 3)
return ans;
Arrays.sort(nums);
for (int i = 0; i < length - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
findTwoSum(nums, i + 1, length - 1, nums[i]);
}
return ans;
}
public void findTwoSum(int[] num, int begin, int end, int target) {
while (begin < end) {
if (num[begin] + num[end] + target == 0) {
List<Integer> list = new ArrayList<Integer>();
list.add(target);
list.add(num[begin]);
list.add(num[end]);
ans.add(list);
while (begin < end && num[begin + 1] == num[begin])
begin++;
begin++;
while (begin < end && num[end - 1] == num[end])
end--;
end--;
} else if (num[begin] + num[end] + target > 0)
end--;
else
begin++;
}
}
}