哈希篇 · 春江花朝秋月夜

字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

重叠数

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(0);
        if (nums1.size()==0||nums2.size()==0){
            return res;
        }
        unordered_set<int> setp;
        unordered_set<int> setq;
        for (int i = 0; i < nums1.size(); ++i) {
            setp.insert(nums1[i]);
        }
        //在前面的数组中出现过
        for (int i = 0; i < nums2.size(); ++i) {
            if (setp.find(nums2[i]) != setp.end()) {
                setq.insert(nums2[i]);
            }
        }
        return vector<int>(setq.begin(),setq.end());
    }
};

两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;//k：元素，v：下标
        for (int i = 0; i < nums.size(); ++i){
            if (map.find(target-nums[i])!=map.end()){
                return {map.find(target-nums[i])->second,i};
            }
            map.insert(pair<int,int>(nums[i], i));
        }
        return {};
    }
};

三数之和

   vector<vector<int>> threeSum(vector<int> &nums) {
        vector<vector<int>> res;
        //排序
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[0] > 0) {
                break;
            }
            unordered_set<int> set;
            //去重
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            for (int j = i + 1; j < nums.size(); ++j) {
                int target = 0 - (nums[i] + nums[j]);
                if (set.find(target) != set.end()) {
                    res.push_back(vector<int>{nums[i], nums[j], target});
                } else {
                    res.push_back(vector<int>{nums[j]});
                }
            }
        }
        return res;
    };

寻找最近的三数之和：

/**

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 */

class Solution {
public:

   int threeSumClosest(vector<int> &nums, int target) {
       sort(nums.begin(), nums.end());
       int len = nums.size();
       int closestNum = nums[0] + nums[1] + nums[2];
       for (int i = 0; i < len; ++i) {
           int j = i + 1;
           int k = len - 1;
           while (j < k) {
               int sum = nums[i] + nums[j] + nums[k];
               if (sum == target) {
                   return target;//刚好相等，直接返回目标元素
               }
               if (abs(target - sum) < abs(target - closestNum)) {
                   closestNum = sum;
               }
               if (sum > target) {
                   k--;
               } else {
                   j++;
               }
           }
       }
       return closestNum;
   }
};

class Solution {
   public int threeSumClosest(int[] nums, int target) {
       Arrays.sort(nums);
       int best=Integer.MAX_VALUE;
       int n=nums.length;//数组长度
       for(int i=0;i<n;i++){
           int j=i+1,k=n-1;
           //二分
           while(j<k){
               int sum=nums[i]+nums[j]+nums[k];
               if(sum==target) return target;//刚好相等，直接返回目标元素
               if(Math.abs(target-sum)<Math.abs(best-target)){
                   best=sum;
               }else if(sum>target){
                   k--;
               }else{
                   j++;
               }
           }
       }
       return best;
   }
}