目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
数组中相加和为0的三元组
访问量:1508
一、简介
给出一个有n个元素的数组S,S中是否有元素a,b,c满足a+b+c=0?找出数组S中所有满足条件的三元组。
注意:
三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)
解集中不能包含重复的三元组。
例如,给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)
二、实现
分析:本题本质三数之和,因为要非降序排列,多了一个排序。
/** * * @param num int整型一维数组 * @return int整型二维数组 */ func threeSum( num []int ) [][]int { // write code here if len(num) < 3 { return nil } // 对数据进行 排序 sort.Ints(num) var ( left = 0 right = len(num) - 1 ) unqMap := make(map[string]bool) rs := make([][]int, 0) for left < right { if num[left] > 0 { break } for j := right; j > left ; j -- { // 判断 left ~ right之间,是否存在一个数字,满足 三元组 seekVal := 0 - num[left] - num[j] for i:= left +1; i < j; i++ { if num[i] != seekVal { continue } if num[i] > seekVal { break } // 因为要去重,满足之前,要判断是否有重复 key := fmt.Sprintf("%d_%d_%d", num[left], num[i], num[j]) if unqMap[key] { continue } // 存在三元组 rs = append(rs, []int{num[left], num[i], num[j]}) unqMap[key] = true } } left ++ for left < right && num[left] == num[left -1] { left ++ } } return rs }
题目来源:牛客
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助