1.两数之和

//暴力解法，时间复杂度为O(n^2)
vector<int> twoSum(vector<int>& nums, int target) {
	int n = nums.size();
    for(int i = 0;i < n;++i){
        for(int j = i+1;j < n;++j){
            if(nums[i] + nums[j] == target){
                return{i,j}
            }
        }
    }
    return{}
}
  • 暴力解法中为了降低时间复杂度，先将nums.size存储到n中
  • ++i比i++更好
  • 返回类型为vector<int>时，用{i,j}返回
//时间复杂度为O(n)
vector<int> twoSum(vector<int>& nums, int target) {
	unordered_map<int,int> hashtable;
    for(int i = 0;i < nums.size();++i){
        auto it = hashtable.find(target - nums[i]);
        if(it != hashtable.end()){
            return{i,it->second};
        }
        hashtable[nums[i]] = i;
    }
    return {};
}
  • 将找target-nums[i]的时间降低了
  • 注意这里使用了hashtable，C++中是用unordered_map来定义hashtable的，注意unordered_map的用法

今天就写到这儿，明天总结vector和unordered_map的用法

15 三数之和

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    int n = nums.size();
    int i,j,k;
    vector<vector<int>> result;
    for(i = 0;i < n-2;++i){
        if(i > 0 && nums[i] == nums[i-1]){//遍历时跳过重复项
            continue;
        }
        k = n - 1;
        for(j = i + 1;j < n - 1;++j){
            if(j > (i + 1) && nums[j] == nums[j-1]){//遍历时跳过重复项
                continue;
            }
            while((k>j)&&((nums[i]+nums[j]+nums[k])>0)){
                --k;
            }
            if(k == j)break;
            if((nums[i]+nums[j]+nums[k])==0){
                result.push_back({nums[i],nums[j],nums[k]});
            }
        }
    }
    return result;
}

  • 排序和i，j遍历时跳过重复项，可以使得答案不包含重复组。（也可用set.find来辅助result不包含重复组，但是空间复杂度提高）

  • 典型的双指针，一前一后，前后两个指针的移动顺序要按照题目的要求，比如15题要求三数之和等于0，那么如果大于0，则后指针要前移；再比如11题要求面积最大，那么应该移动对应高度低的指针，使得面积不缩小。

  • result.push_back({nums[i],nums[j],nums[k]});//可以用这种形式来赋值二维向量