題目資訊
源地址：三數之和
給你一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0，請你找出所有和為 0 且不重復的三元組，
注意：答案中不可以包含重復的三元組，
提示資訊
示例 1
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
示例 2
輸入：nums = []
輸出：[]
示例 3
輸入：nums = [0]
輸出：[]
限制
0 <= nums.length <= 3000-105 <= nums[i] <= 105
實作邏輯
暴力列舉
最先想到的應該是暴力列舉的方法，當然這也是最簡單的的方法，
既然這里要找出符合要求的三個數，當然是使用三層回圈依次去匹配，缺點就是時間復雜度達到了 \(O(n^3)\)，當陣列長度特別長的時候，程式運行時間也會特別長，
哈希匹配
從“兩數之和”題目中可以知道，使用哈希表結構采用空間換時間的方式，時間復雜度能從 \(O(n^2)\) 降到了 \(O(n)\)，
如果將這種空間換時間的方式代入這個題目，可以將暴力破解 \(O(n^3)\) 的時間復雜度降到 \(O(n^2)\)，這也是一個非常大的提升，
排序 + 雙指標
現在思考一下如何將時間復雜度從 \(O(n^2)\) 降下去，
- 首先一層回圈是必不可少的，因為至少要對給定的陣列做一次列舉；
- 假如拿到陣列的第一個元素，需要思考一下怎么從陣列剩下的元素中找到匹配的兩個元素，換一個思路其實就是從剩下的陣列元素中找到和等于第一個元素相反數的兩個元素，所以這里退變成了“兩數之和”的邏輯；
- 如果對剩下的元素采用哈希匹配的方法，其實就和上面的方法一致了，由于答案中不可以包含重復的三元組，這里先對陣列進行排序，方便后續跳過相同的答案，再采用陣列首尾雙指標的方法查找匹配的兩個數，
package cn.fatedeity.algorithm.leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public List<List<Integer>> answer(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
// 答案不可以包含重復的三元組，這里相同的數直接過掉
continue;
}
int target = -nums[i];
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int diff = target - (nums[left] + nums[right]);
if (diff > 0) {
left++;
} else if (diff < 0) {
right--;
} else {
boolean leftFlag = left == 0 || nums[left] != nums[left - 1];
boolean rightFlag = right == nums.length - 1 || nums[right] != nums[right + 1];
if (leftFlag || rightFlag) {
// 這里的 if 判斷仍然是避免答案出現重復的三元組
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
}
left++;
right--;
}
}
}
return result;
}
}
使用這個方式解決這個題目，耗時的地方有兩個：對原陣列進行排序；對排序后的陣列查找出和為目標數的兩個數，
排序的時間復雜度可以看做是 \(O(n\log_2n)\)，查找出剩余兩個數采用了遍歷陣列并嵌套使用雙指標遍歷，時間復雜度為 \(O(n \times n)\)，最終總體的時間復雜度在 \(O(n^2)\)，
在整個程序當中，除了存盤答案需要額外的空間，實際的空間復雜度是 \(O(1)\)，
首發于翔仔的個人博客，點擊查看更多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502572.html
標籤：其他