【問題描述】[中等]

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組。注意：答案中不可以包含重復的三元組。 示例：給定數組 nums = [-1, 0, 1, 2, -1, -4]，滿足要求的三元組集合為： [[-1, 0, 1],[-1, -1, 2] ]

【解答思路】

排序+雙指針

時間復雜度：O(N^2) 空間復雜度：O(1)

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for(int k = 0; k < nums.length - 2; k++){if(nums[k] > 0) break;if(k > 0 && nums[k] == nums[k - 1]) continue;int i = k + 1, j = nums.length - 1;while(i < j){int sum = nums[k] + nums[i] + nums[j];if(sum < 0){while(i < j && nums[i] == nums[++i]);} else if (sum > 0) {while(i < j && nums[j] == nums[--j]);} else {res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));while(i < j && nums[i] == nums[++i]);while(i < j && nums[j] == nums[--j]);}}}return res;} }

【總結】

1. 審題 特殊條件進行優化

2.細節

List list = Arrays.asList(“a”,“b”,“c”);
將數組轉化成List集合的方法

轉載鏈接：https://leetcode-cn.com/problems/3sum/solution/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/

參考鏈接：https://blog.csdn.net/kzadmxz/article/details/80394351

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第15题][三数之和][数组][双指针]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。