三数之和

问题描述:

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
本题需要注意:1、三个元素a+b+c=0
2、vector内可能存在重复元素,但是返回结果中不允许重复

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum

思路:

1、找到a+b+c=0的组合
首先,对vector进行排序。
三个数之中必须存在至少一个小于0的数,否则无法保证三个数的和为0;
第一个数a从0到n-2遍历(因为vector已经从大到小排序,所以必须保证a<0);第二个数b从a的下一个位置first开始;第三个数c从n-1开始。
如果a+b+c<0,b太小,所以first向后移,first++;如果a+b+c>0,c太大,所以last向前移,last--;否则,将a、b、c插入到vec中。
在first和last移动的过程中,必须保证first<last;
2、在这过程中可能会出现重复->去重
每次在进行操作的时候只取相同的数较左边的那个(右边的相同数字,跳过即可)。

题解:


class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<int> B;
        vector<vector<int>> A;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int first;
        int last;
        for (int i = 0; i < n - 2 && nums[i] <= 0; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            first = i + 1;
            last = n - 1;
            while (first < last) {
                if (nums[i] + nums[first] + nums[last] > 0) {
                    last--;
                } else if (nums[i] + nums[first] + nums[last] < 0) {
                    first++;
                } else {
                    B.push_back(nums[i]);
                    B.push_back(nums[first]);
                    B.push_back(nums[last]);
                    A.push_back(B);
                    B.clear();
                    first++;
                    while (first < last && nums[first] == nums[first - 1]) {
                        first++;
                    }
                }
            }

        }
        return A;
    }
};

vector

vector和数组的区别:

相同点:
1、拥有的类型是以一样的,如int,string
2、都可以用下标直接进行操作
3、都可以用迭代器进行操作(在c++中每个容器都配有各自的迭代器)
不同点:
1、(vector)长度不固定,可以随时进行扩容
(数组)在定义的长度已经固定,如int array[100]
2、(vector)用size得到长度(因为你也不知道扩容以后是多大)
(数组)不可以获取,在定义时已经确定了长度
3、(vector)可以在末尾添加vector的元素
(数组)不能增加长度以外的元素
4、(vector)可以确定长度,节约空间
(数组)不能确定长度,必须在定义时定义一个很大的空间留给数组,造成内存的浪费
5、(vector)在给二维数组赋值的时候,vector不可以用vector43= tmp直接赋值,而要用vector<int>A,vector<vector<int>>B,A.push_back()...B.pushback()进行对B的赋值。
(数组)数组可以直接用array43直接赋值

关于vector的一一丢丢内部机制

初始化(根据实际,平时会经常用到的初始化vector的方法):
1、vector<int> vec;
默认初始化,size为0,容器中没有元素,容量也为0,还没有分配内存空间。
2、vector<int> vec1(vec);vector<int> vec1=vec;
vec1的类型必须与vec的类型相同。vec1将与vec有相同的容量以及元素。
3、vector<int> vec={1,2,3,4,8.9}
其中列表中的元素不一定必须为int类型,但必须类型相容。如int型1,2,3,4可以直接拷贝,其他类型会进行转化
4、vector<int> vec(9);
vec中将包含9个元素,每个元素进行缺省的值进行初始化,如int的初始化是0,因此vec中是9个0;
5、vector<int> vec(9,8)
vec中将包含9个元素,每个元素初始化为8,因此vec中是9个8;

扩容

在扩容的时候,动态申请内存,如最初始的容量是1,扩容的时候,申请1×2(即2倍)的内存空间,如果不够,再次申请2×2(即2倍)的内存空间,然后将原空间元素通过复制的方式初始化新空间,再向新空间增加元素,最后析构并释放原空间。

一些基本的常用的操作

1、插入:vec.push_back(elem)
2、删除:vec.pop_back
3、获取起始数据:vec.front()
4、获取末尾元素:vec.back()
5、得到大小:vec.size()
6、设置大小:vec.resize()
7、排序:sort(vec.begin(),vec.end())
8、去重:erase(unique(vec.begin(),vec.end()),vec.end())
9、清空:vec.clear()