数据结构——哈希表leetcode题目

【leetcode 242】

���定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"输出: true

示例 2:

输入: s = "rat", t = "car"输出: false

提示:

• 1 0) { sum+=pow((n%10),2); n/=10; }; return sum; }};

  [leetcode 1]

  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

  你可以按任意顺序返回答案。

  示例 1：

  输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

  示例 2：

  输入：nums = [3,2,4], target = 6输出：[1,2]

  示例 3：

  输入：nums = [3,3], target = 6输出：[0,1]

  提示：

  • 2 0) { break; } if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重 continue; } unordered_set set; for (int j = i + 1; j i + 2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2]) { // 三元组元素b去重 continue; } int c = 0 - (nums[i] + nums[j]); if (set.find(c) != set.end()) { result.push_back({nums[i], nums[j], c}); set.erase(c);// 三元组元素c去重 } else { set.insert(nums[j]); } } } return result; }};

    下面是双指针法的代码实现

    class Solution {public:    vector threeSum(vector& nums) {        vector result;        sort(nums.begin(), nums.end());        // 找出a + b + c = 0        // a = nums[i], b = nums[left], c = nums[right]        for (int i = 0; i  0) {                return result;            }            // 错误去重a方法，将会漏掉-1,-1,2 这种情况            /*            if (nums[i] == nums[i + 1]) {                continue;            }            */            // 正确去重a方法            if (i > 0 && nums[i] == nums[i - 1]) {                continue;            }            int left = i + 1;            int right = nums.size() - 1;            while (right > left) {                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right left && nums[right] == nums[right - 1]) right--;                while (right > left && nums[left] == nums[left + 1]) left++;                */                if (nums[i] + nums[left] + nums[right] > 0) right--;                else if (nums[i] + nums[left] + nums[right]  left && nums[right] == nums[right - 1]) right--;                    while (right > left && nums[left] == nums[left + 1]) left++;                    // 找到答案时，双指针同时收缩                    right--;                    left++;                }            }        }        return result;    }};

    [leetcode 18]

    四数之和

    给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

    • 0 left) { // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出 if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) { right--; // nums[k] + nums[i] + nums[left] + nums[right] left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } } return result; }};