C++刷题笔记(9)——leetcode1、383

解题思路：
创建一个哈希表，对于数组中的元素x，在哈希表中查询是否存在target-x，如果有则返回x和target-x在数组中的下标；如果没有则将x放入哈希表中，继续遍历数组

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        std::unordered_map  hash;              //反过来放，因为根据值返回下标
        for (int i = 0; i < nums.size(); i++) {          //遍历数组
            auto iter = hash.find(target - nums[i]);     //auto 由编译器来识别变量的类型
            if (iter != hash.end()) {                    //hash表中找到等于target-nums[i]的值
                return { iter->second, i };              //->second指向index
            }
            hash.insert(pair(nums[i], i));     //反过来放入hash表中，用来获取结果下标
        }
        return {};                                       
    }
};

两个for循环走天下

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        int 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 {};
    }
};

解题思路：
遍历两个字符串，如果在ransomNote中找到和magazine相同的字符，就把它删掉，这样ransomNote中的字符会随着遍历越来越少，如果最后删完了，就说明在ransomNote的字符、magazine里都有，就可以由magazine组成ransomNote。

class Solution {
public:
	bool canConstruct(string ransomNote, string magazine) {
		for (int i = 0; i < magazine.length(); i++) {
			for (int j = 0; j < ransomNote.length(); j++) {
				// 在ransomNote中找到和magazine相同的字符
				if (magazine[i] == ransomNote[j]) {
					ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
					break;
				}
			}
		}
		// 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
		if (ransomNote.length() == 0) {
			return true;
		}
		return false;
	}
};

用长度为26的数组记录magezine中字符出现的次数，然后再用ransomNote言这个数组是否包含了ransomNote所需要的所有字母。

class Solution {
public:
	bool canConstruct(string ransomNote, string magazine) {
		int record[26] = { 0 };
		for (int i = 0; i < magazine.length(); i++) {
			// 通过recode数据记录 magazine里各个字符出现次数
			record[magazine[i] - 'a'] ++;
		}
		for (int j = 0; j < ransomNote.length(); j++) {
			// 遍历ransomNote，在record里对应的字符个数做--操作
			record[ransomNote[j] - 'a']--;
			// 如果小于零说明ransomNote里出现的字符，magazine没有
			if (record[ransomNote[j] - 'a'] < 0) {
				return false;
			}
		}
		return true;
	}
};