企业官网建设流程全解析

【python3&&Java】leetcode.15三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题思路

在用哈希表来处理该问题会十分困难会很容易出现bug，而利用双指针来解决该问题会变得很高效。

python3

classSolution:defthreeSum(self,nums:list[int])->list[list[int]]:nums.sort()result=[]foriinrange(len(nums)):ifnums[i]>0:returnresult# 跳过相同的元素以避免重复ifi>0andnums[i]==nums[i-1]:continueright=len(nums)-1left=i+1whileright>left:sum_=nums[i]+nums[left]+nums[right]ifsum_<0:left+=1elifsum_>0:right-=1else:result.append([nums[i],nums[left],nums[right]])whileright>leftandnums[right]==nums[right-1]:right-=1whileright>leftandnums[left]==nums[left+1]:left+=1right-=1left+=1returnresult

Java

class Solution {//哈希表去重复杂，双指针效率高 public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); // 先排序 List<List<Integer>> res = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { // 跳过重复元素 if (i > 0 && nums[i] == nums[i - 1]) continue; // 双指针，目标是找到 nums[l] + nums[r] = -nums[i] int l = i + 1, r = nums.length - 1; int target = -nums[i]; while (l < r) { int sum = nums[l] + nums[r]; if (sum == target) { res.add(Arrays.asList(nums[i], nums[l], nums[r])); l++; r--; // 跳过重复元素 while (l < r && nums[l] == nums[l - 1]) l++; while (l < r && nums[r] == nums[r + 1]) r--; } else if (sum < target) { l++; } else { r--; } } } return res; } }

特别注意

题干要求中有去重的要求，所以在代码实现的过程中我们需要十分小心重复元素的去重