C/C++教程

(二)双指针(C++刷题)

本文主要是介绍(二)双指针(C++刷题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

三数之和

Leetcode:https://leetcode-cn.com/problems/3sum/

1.问题描述

给定一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a+b+c=0?找出所有和为0且不重复的三元组。

2.输入输出

  • 输入:nums=[-1,0,1,2,-1,-4]
  • 输出:[[-1,-1,2], [-1,0,1]]

3.算法分析

【排序+双指针】

  • 特判,对于数组长度 n,如果数组为null或者数组长度小于3,返回 [][]。
  • 对数组进行排序。
  • 遍历排序后数组:
    • 若 nums[i]>0:因为已经排序好,所以后面不可能有三个数加和等于0,直接返回结果。
      对于重复元素:跳过,避免出现重复解
    • 令左指针 L=i+1,右指针 R=n-1,当 L<R时,执行循环:
      • 当 nums[i]+nums[L]+nums[R]==0,执行循环,判断左界和右界是否和下一位置重复,去除重复解。并同时将 L,R 移到下一位置,寻找新的解
      • 若和大于 0,说明 nums[R] 太大,R 左移
      • 若和小于 0,说明 nums[L] 太小,L 右移
  • 时间复杂度:\(O(n^2)\)
  • 空间复杂度:\(O(1)\)

4.编程实现

#include <iostream> 
#include <algorithm>
#include <vector> 
using namespace std; 


class Solution{
public:
    vector<vector<int>> threeSum(vector<int>& nums){
        vector< vector<int> > ans;
        if(nums.size() < 3 || nums.empty()) return ans; // 特判
        int n = nums.size();
    
        sort(nums.begin(), nums.end()); //排序
        for(int i = 0; i < n; i++)  // 枚举最小值
        {
            if(nums[i] > 0) return ans;
            if(i > 0 && nums[i] == nums[i-1]) continue;   // 最小元素去重!
            int l = i+1;
            int r = n-1;
            while(l < r)    // 枚举中间值和最大值
            {
                int x = nums[l] + nums[r] + nums[i];
                if(x == 0){ // 符合条件,存储,并且去重,双端都移到下一个位置
                    ans.push_back({ nums[i], nums[l], nums[r] });
                    while( l < r && nums[l] == nums[l+1]) l++; l++;
                    while( l < r && nums[r] == nums[r-1]) r--; r--;
                }
                else if(x > 0) // 大了就让右边最大值变小
                    r--;
                else        // 小了就让左边中间值变大
                    l++;
            }
        }
        return ans;
    }
};

int main() { 
    int get;
    Solution sol;
    vector<int> nums; 
    
    getchar();
    while (cin >> get) { 
        nums.push_back(get); 
        if (cin.get() == ']') break; 
    } 
    
    cout << sol.threeSum(nums)[0][0] << endl; 
    return 0; 

} 

无重复字符的最长子串

Leetcode:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

1.问题描述

给定一个字符串s,找出其中不含有重复字符的最长子串的长度。

2.输入输出

  • Input:"abcabcbb"
  • Output:3

3.算法分析

滑动窗口:核心思想就是从每一个字符开始,找到不包含重复字符的最长子串。每次移动区间的起点或者终点,直到起点的值等于终点的值。

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

4.编程实现

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), length(0), result(0);
        int nSize = s.size();
        
        while (end < nSize) {  // 终点
            char tmpChar = s[end];
            for (int index = start; index < end; index++) {
                if (tmpChar == s[index]) {
                    start = index + 1;
                    length = end - start;
                    break;
                }
            }
            end++;
            length++;
            result = max(result, length);
        }
        
        return result;
    }
};

int main() {
    Solution sol;
    string s;
    cin >> s;
    
    cout << sol.lengthOfLongestSubstring(s) << endl;
    return 0;
}
这篇关于(二)双指针(C++刷题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!