[LeetCode]15.3Sum

本文主要是介绍[LeetCode]15.3Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

    For example, given array S = {-1 0 1 2 -1 -4},A solution set is:(-1, 0, 1)(-1, -1, 2)

Discuss

【题意】

给定n个整数的数组S，是否在 数组S中有元素a，b，C，使得A + B + C =0？在数组中找出独一无二的三元素组，使得他们之和为0。

注意：

在三元素组（A，B，C）中，必须满足非递减排序。 （即A≤B≤C）

该解决方案集中一定不能包含重复的三元素组。

【分析】

先排序，然后二分查找，复杂度 O(n^2*log n)。a + b + c = 0 即 b + c = -a   

题目思路与 剑指Offer之和为S的连续正数序列 博文思路一致。可以参考一下解题思路。

另有：点击打开链接  详细总结

【代码】

/*********************************
*   日期：2014-01-18
*   作者：SJF0115
*   题目: 15.3Sum
*   网址：http://oj.leetcode.com/problems/3sum/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:vector<vector<int> > threeSum(vector<int> &num) {int i,j,target,start,end;int Len = num.size();vector<int> triplet;vector<vector<int>> triplets;//排序sort(num.begin(),num.end());for(i = 0;i < Len-2;i++){//跳过重复元素if(i != 0 && num[i] == num[i-1]){continue;}//a + b + c = 0target = -num[i];//二分查找start = i + 1;end = Len - 1;while(start < end){int curSum = num[start] + num[end];//相等 -> 目标if(target == curSum){triplet.clear();triplet.push_back(num[i]);triplet.push_back(num[start]);triplet.push_back(num[end]);triplets.push_back(triplet);//注意： 跳过重复元素while(start < end && num[start] == num[start + 1]){start ++;}while(start < end && num[end] == num[end - 1]){end --;}start ++;end --;}//大于 -> 当前值小需要增大else if(target > curSum){//注意：跳过重复元素while(start < end && num[start] == num[start + 1]){start ++;}start ++;}//小于 -> 当前值大需要减小else{//注意：跳过重复元素while(start < end && num[end] == num[end - 1]){end --;}end --;}}//while}//forreturn triplets;}
};
int main() {vector<vector<int>> result;Solution solution;vector<int> vec;vec.push_back(-2);vec.push_back(0);vec.push_back(0);vec.push_back(2);vec.push_back(2);result = solution.threeSum(vec);for(int i = 0;i < result.size();i++){for(int j = 0;j < result[i].size();j++){printf("%d ",result[i][j]);}printf("\n");}return 0;
}

【测试】

这篇关于[LeetCode]15.3Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！