136 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

题目看这里

解题思路——位运算

1. hash表

```c++ class Solution { public: int singleNumber(vector& nums) { int ans=0; unordered_map<int,int> hash; for(int num:nums){ hash[num]++; } for(int num:nums){ if(hash[num]==1){ ans=num; } } return ans; } };

2. **位运算**：通过连续异或运算，可是将出现两次的数字值变为0

```c++
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans=0;
        for(int num:nums){
            ans=ans^num;
        }
        return ans;
    }
};

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素

题目看这里

解题思路——hashmap

```c++ class Solution { public: int majorityElement(vector& nums) { unordered_map<int,int> hash; int n=size(nums); for(int num:nums){ hash[num]++; if(hash[num]>(n/2)) return num; } return -1; } };

# 15. 三数之和

给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请

你返回所有和为 `0` 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

<a href="https://leetcode.cn/problems/3sum/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=1hi0xhg">题目看这里</a>

## 解题思路

1. 排序+双指针

```c++
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};