題目描述
1. 三數之和
給你一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組，
注意：答案中不可以包含重復的三元組，
示例:
給定陣列 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[[-1, 0, 1],[-1, -1, 2]]
題目決議
- 要求a + b + c = 0 ==> a + b = -c
- 陣列無序且存在重復元素，但是結果中不可以包含重復的三元組
- 可能沒有滿足條件的情況，回傳空陣列
方法一：暴力法
解題思路
采用三層回圈的方式，最外層回圈固定一個元素 nums[i] ，第二層回圈從元素 nums[i]下一個元素 j = i + 1，nums[j] 開始遍歷，第三層回圈則從元素 nums[j]下一個元素 k = j + 1，nums[k] 開始遍歷，然后判斷三個元素相加是否滿足以下條件：nums[i] + nums[j] + nums[k] == 0
代碼示例
Java:
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length <= 2) {
return new ArrayList<List<Integer>>();
}
Arrays.sort(nums);
Set<List<Integer>> result = new LinkedHashSet<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> value = https://www.cnblogs.com/liuzhenbin/p/Arrays.asList(nums[i], nums[j], nums[k]);
result.add(value);
}
}
}
}
return new ArrayList<>(result);
}
復雜度分析
時間復雜度：O(n^3)
空間復雜度：O(1)
方法二：哈希表
解題思路
題目要求為a + b + c = 0可以推出 a + b = -c ，將三數之和轉化為兩數求和的問題，外層回圈固定某個元素 nums[i] ，然后再剩下的元素中找到兩個元素相加等于-nums[i]的情況，
代碼示例
Java:
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length <= 2) {
return new ArrayList<List<Integer>>();
}
Set<List<Integer>> result = new LinkedHashSet<>();
for (int i = 0; i < nums.length - 2; i++) {
int target = -nums[i];
Map<Integer, Integer> hashMap = new HashMap<>(nums.length - i);
for (int j = i + 1; j < nums.length; j++) {
int v = target - nums[j];
Integer exist = hashMap.get(v);
if (exist != null) {
List<Integer> list = Arrays.asList(nums[i], exist, nums[j]);
list.sort(Comparator.naturalOrder());
result.add(list);
} else {
hashMap.put(nums[j], nums[j]);
}
}
}
return new ArrayList<>(result);
}
復雜度分析
時間復雜度：O(n^2)
空間復雜度：O(n)
方法二：雙指標法
解題思路
有方法二中可以得知 a + b = -c，在外層回圈中固定元素 nums[i] ，然后再剩余元素中找到兩元素相加和為-nums[i]的情況，此時若將陣列元素有序，則可通過雙指標的方式進行元素遍歷，加快元素查找，
陣列有序，若nums[i]>0，則后續陣列元素必大于零，不可能滿足條件；否則使用雙指標l=i+1和r=len-1遍歷陣列剩余元素；
若 nums[l]+nums[r]+nums[i] > 0 則高位指標r向中間移動，否則低位指標l向中間移動；
若 nums[l]+nums[r]+nums[i] = 0 則通過判斷l、r指標與其前/后元素是否相同加速指標移動，
代碼示例
Java：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length <= 2) {
return res;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if ( sum == 0) {
res.add(Arrays.asList(nums[i],nums[l],nums[r]));
while (l<r && nums[l] == nums[++l]);
while (l<r && nums[r] == nums[--r]);
} else if (sum < 0) {
l++;
} else if (sum > 0) {
r--;
}
}
}
return res;
}
復雜度分析
時間復雜度：O(n^2)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67592.html
標籤：其他