力扣 hot 100 —— 15.三数之和

题目描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

解法思路：

        // 定位一个 + 双指针遍历查找

        // 选定一个，然后在剩余中查找满足条件，为了好判断移动方向，可对数组进行排序

        // 当三者和大于0，则缩小即右指针左移

        // 当三者和小于0，则放大即左指针右移

        // 当移动完，则移动定位进行下一轮

        // 注意进行去重，即定位数字一样则跳过，同理组合数子一样也需要跳过

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 哈希 + 双指针  双指针遍历，哈希表查找对比
        // 左右指针求和，与0做差，在哈希表中查找，找到则输出一个三元组
        // 未找到则进行移动； 当左右和为负数，表示需要一个大的整数，找不到则证明这个组合太小，则移动左右较小的一个，放大这个负数
        // 如果是正数则移动较大的，缩小这个和（正数）

        // unordered_map<int,int> search_map;
        // int left = 0;
        // int right = nums.size() - 1;
        // for(int i = 0 ; i < nums.size(); i++){
        //     search_map[nums[i]] = i;  // 初始化哈希表
        // }
        // vector<vector<int>> result;

        // while(left < right){

        //     int sub_num = 0 - (nums[left] + nums[right]);
        //     auto it = search_map.find(sub_num);
        //     if(it != search_map.end()){
        //         if(it->second != left && it->second != right){
        //             result.push_back({nums[left],nums[right],nums[it->first]});
        //             --right;
        //         }
        //     }
        //     else if((nums[left] + nums[right]) > 0){
        //         if(nums[left] >= nums[right]){
        //             ++left;
        //         }
        //         else{
        //             --right;
        //         }
        //     }
        //     else if((nums[left] + nums[right]) < 0){
        //         if(nums[left] <= nums[right]){                   
        //             --right;
        //         }
        //         else{
        //             ++left;
        //         }
        //     }  

        // }
        // return result;

        // 定位一个 + 双指针遍历查找
        // 选定一个，然后在剩余中查找满足条件，为了好判断移动方向，可对数组进行排序
        // 当三者和大于0，则缩小即右指针左移
        // 当三者和小于0，则放大即左指针右移
        // 当移动完，则移动定位进行下一轮
        // 注意进行去重，即定位数字一样则跳过，同理组合数子一样也需要跳过

        vector<vector<int>> result;
        sort(nums.begin(),nums.end()); // 排序默认升序
        // 此处定义，防止循环中定义，会重复
        int left = 0; 
        int right = 0;
        
        // 遍历定位数
        for(int a = 0; a<nums.size();++a){
            if(a>0 && nums[a] == nums[a-1]){ // 存在重复
                continue;
            }
            left = a + 1;
            right = nums.size() - 1;
            while(left < right){
                if((nums[a] + nums[left] + nums[right]) == 0){
                    result.push_back({nums[a] , nums[left] , nums[right]});
                    ++left;
                    while(left < right && nums[left-1] == nums[left]){
                        ++left;
                    }
                }
                else if((nums[a] + nums[left] + nums[right]) < 0){
                    ++left;
                }
                else{
                    --right;
                }

            }
        
        }
        return result;
        
    }
};