给定一个不存在重复元素的数组,输出其中所有满足a + b = c 的三元组 <a, b, c> 个数。
做的时候没考虑到负数的情况。。。。肯定有很多人和我一样
import java.util.*; public class Solution { public int NumberOfTriplets (int[] nums) { int res = 0, n = nums.length; Arrays.sort(nums); for (int i = 0; i < n; i++) { int lo = 0, hi = n - 1; while (lo < hi) { if (lo == i) lo++; else if (hi == i) hi--; if (lo >= hi) break; int sum = nums[lo] + nums[hi]; if (sum == nums[i]) { res++; while (lo < hi && nums[lo] == nums[lo + 1]) lo++; while (lo < hi && nums[hi] == nums[hi - 1]) hi--; lo++; hi--; } else if (sum > nums[i]) { hi--; } else { lo++; } } } return res; } }
class Solution: def count(self, list1, n): cnt1 = 0 for i in range(len(list1)-1): for j in range(i+1, len(list1)): if list1[i]+list1[j] == n: cnt1 += 1 return cnt1 def NumberOfTriplets(self, arr): if len(arr) <= 2: return 0 elif len(arr) >= 3: arr.sort() cnt = 0 for i in range(2, len(arr)): cnt += self.count(arr[:i], arr[i]) return cnt
int NumberOfTriplets(vector<int>& arr){ int num=0; if(arr.size()<3){ return num; }else{ for (int i=0; i<arr.size(); i++) { for (int j=i+1; j<arr.size(); j++) { for (int h=0; h<arr.size(); h++) { if(arr[h]!=arr[i]&&arr[h]!=arr[j]){ if (arr[i]+arr[j]==arr[h]) { num++; } } } } } } return num; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param arr int整型一维数组 * @return int整型 */ public int NumberOfTriplets (int[] arr) { int len = arr.length; if (len < 3) { return 0; } Set<Integer> set = new HashSet<>(); for (int num : arr) { set.add(num); } int ans = 0; for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { int sum = arr[i] + arr[j]; if (sum != arr[i] && sum != arr[j] && set.contains(sum)) { ans++; } } } return ans; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param arr int整型一维数组 * @return int整型 */ public int NumberOfTriplets (int[] arr) { // write code here int res = 0; int len = arr.length; if(len < 3){ return 0; } Arrays.sort(arr); /** 先对数组进行排序; 倒序遍历数组,将数组的每个元素视为target; 用双指针的方法,寻找数组中 a+b = target 的组合数量; a、b、target是不重复的三个数; 如:对于已经排序好的数组 [-3,-2,-1,0,1,2,3] 3+0=3 这种情况是不行的; */ for(int i=len-1;i>=0;i--){ int temp = check(arr,0,len-1,i,arr[i]); res += temp; } return res; } int check(int[] arr ,int left,int right,int i,int target){ int ans = 0; while(left < right){ if(left == i){ left++; continue; } if(right == i){ right--; continue; } int sum = arr[left] + arr[right]; if(sum == target){ ans++; left++; right--; }else if(sum < target){ left++; }else{ right--; } } return ans; } }