LeetCode 解题笔记（二）数组篇_class solution { public: vector twosum(vector

---

总目录:      LeetCode 解题笔记（一）总

---

一、基础篇

26.删除排序数组中的重复–2022/01/16

链接： 26.删除有序数组中的重复项

题目： 简单

标签： 数组、快慢指针

题解： 逆向思维！判断每一个不相等的数，并计数，答案就出来了！！！

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() <=0 )
            return 0;
        int c = 0;
        nums[c++] = nums[0];

        for(int i=1; i<nums.size(); i++) {
            if(nums[i] != nums[i-1])
                nums[c++] = nums[i];
        }
        return c;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

官方

思路： 快慢指针

定义两个指针 fast 和 slow 分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

122. 买卖股票的最佳时机 II–2022/01/17

链接：122. 买卖股票的最佳时机 II

题目： 中等

**标签：**数组、动态规划、贪心

我的答案：

思路：暴力解法，考虑边界条件，然后试错得出，效果还行：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minp = prices[0], maxp= 0;
        int sum = 0, n=prices.size();

        for(int i=1; i<n; i++) {
            if(prices[i] <= prices[i-1]) {
                if(maxp) {  
                    sum += maxp - minp;   //存在了最大利润了，并且这次又是新的最小值买入时机
                    maxp = 0;
                }
                minp = prices[i];         //最小值买入时机
            }
            else {
                maxp = prices[i];             //保存当前的最大利润
                // minp = prices[i-1];        //不需要的，试错出来的
                if(i == n-1) { 
                    sum += maxp - minp;       //最大值结束的话，得计算一遍
                }
            }
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度：O(n)，其中 n 为数组的长度。我们只需要遍历一次数组即可。
空间复杂度：O(1)，只需要常数空间存放若干变量。

参考答案：

看动态规划比较累，看这个贪心太舒服了：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-tong-su-yi-dong-de-ti-ji-avcz/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for(int i = 0; i < prices.size() - 1; i++)
            if(prices[i + 1] > prices[i])
                res += prices[i + 1] - prices[i];
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10

---

---

189. 轮转数组–2022/01/18

链接：189. 轮转数组

题目： 中等

标签： 数组

我的答案： 最容易想到的：建立个临时的数组

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(nums.size() == 0) return;
        int n= nums.size();

        vector<int> tmp ;           // vector<int> tmp = {0}; 这样初始化就已经添加了一个值
        for(const auto& num: nums){
            tmp.push_back(num);
        }
        for(int i=0; i<n; i++) {
            nums[(i+k)%n] = tmp[i];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

官方：若干答案，后续补充…

---

217. 存在重复元素–2022/01/19

链接：217. 存在重复元素

标签： 数组、排序、哈希表

题目：

我的答案：

**思路：**应该是最快的一次呢，排序+遍历判断就好！

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        int n = nums.size();
        if(n==0 || n==1) return false;

        //快速排序
        std::sort(nums.begin(), nums.end());
        for(int i=1; i<n; i++) {
            if(nums[i] == nums[i-1]) return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

官方：

思路：哈希表，对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for (int x: nums) {
            if (s.find(x) != s.end()) {
                return true;
            }
            s.insert(x);
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---

---

136. 只出现一次的数字–2021/12/14

标签：位运算、异或
题目：136. 只出现一次的数字

思路：

异或特性（异或是找不同！）：
① 任何数与0异或，都是它本身
② 任何数与自身异或，都是0
③ 满足交换律、结合律

所以两个一样的数都可以消掉，然后单独的数与0异或

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(const auto& num: nums) {
            ret ^= num;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10

---

350. 两个数组的交集 II – 2022/01/12

题目：350. 两个数组的交集 II

标签： 数组、哈希表、双指针、二分查找、排序

方法一：我的思路： 先排序，后用双指针…

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()==0 || nums2.size()==0) return {};
        
        //先排序
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());

        int i1=0,i2=0;
        int n1 = nums1.size(), n2 = nums2.size();
        vector<int> ret;
    
        //双指针
        while((i1!=n1) && (i2!=n2)) {
            if(nums1[i1] < nums2[i2]) {
                ++i1;
            }
            else if(nums1[i1] > nums2[i2]) {
                ++i2;
            }
            else {
                ret.push_back(nums1[i1]);
                ++i1;
                ++i2;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

方法二：参考官方的哈希表方法后写的：

1636 有点相似

首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        //调整为 num1 为短的数组， 高级技巧
        if(nums1.size() > nums2.size()) {
            intersect(nums2, nums1);
        }
        
        //添加 num1 到哈希表中, 键-值类型，且无序的，用 unordered_map
        unordered_map<int,int> map;
        for(const auto& num: nums1) {
            ++map[num];            //不用指定多大空间的？
        }

        unordered_map <int, int> m;
        for (int num : nums1) {
            ++m[num];
        }

        //判断 num2 中
        vector<int> ret;
        for(const auto& num: nums2) {
            if(map.count(num)) {  //判断键有木有
                --map[num];
                if(map[num] == 0) {  //减到了 0 了
                    map.erase(num); //删除之
                } 
                ret.push_back(num); //添加一次
            }
        }
        return ret;
    };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

66. 加一 – 2022/01/20

链接：66. 加一

题目： 简单

标签： 数组、数字

我的答案：

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        if(n==0) { return {}; }

        bool carry = true; //最高位进位

        for(int i=n-1; i>=0; i--) {
            if(carry) {
                if( digits[i] == 9) {
                    digits[i] = 0;
                    carry = true;
                }
                else {
                    digits[i]++;
                    carry = false;
                }
            }
        }

        if(carry) {
            vector<int> ret(n + 1);
            ret[0] = 1;
            return ret;
        }

        return digits;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

！官方的答案复杂了，不贴了

参考网友的，很简洁，就发现我的 array 很没必要！

public int[] plusOne(int[] digits) {
      int n = digits.length;
      for (int i = n - 1; i >= 0; i--) {
          if (digits[i] == 9) {
              digits[i] = 0;
          } else {
              digits[i] += 1;
              return digits;
          }
      }
      int[] ans = new int[n + 1];
      ans[0] = 1;
      return ans;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

1.两数之和（2022/01/20）

链接： 1. 两数之和

题目：

标签： 哈希，数组

思路：

我的暴力解题：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    	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 {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我的双指针：（错误答案）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //1.排序
        std::sort(nums.begin(), nums.end());
        
        //2.双指针
        int left = 0, right = nums.size()-1;
        vector<int> ret;
        while(left < right) {
            int t = nums[left] + nums[right];
            if(t == target) {
                ret.push_back(left);
                ret.push_back(right);
                break;
            }
            else if(t < target) {
                left ++;
            }
            else {
                right --;
            }
        }

        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

然而，是要返回数组的下表的，所以此方法不适应，考虑哈希才是最快的！ 用哈希的 count 方法

map.count(Key) 返回值为1或者0，1返回存在，0返回不存在

网友答案：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> _map;    //        unordered_map<int,int> _map; 都行
        vector<int> b(2,-1); //用来承载结果，初始化一个大小为2，值为-1的容器b

        for(int i=0; i<nums.size() ; i++) {
            //从第二个数开始寻找哈希表中是否有对应的 key
            if(_map.count(target-nums[i])) {
                b[0] = _map[target-nums[i]];
                b[1] = i;
                break;
            }

            //第一次的时候，反过来存入键值，为了count函数
            _map[nums[i]] = i;  //第一次存入了 （3,0） 第二次（2,1）
        }
        return b;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20