8.8 哈希表简单 1 Two Sum 141 Linked List Cycle

1 Two Sum

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//给的target是目标sum 要返回vector<int> res(2,0);是在num中找加数//首先假设每个输入都是由唯一的结果，而且不适用相同的元素两次一共有n*(n-1)种情况//按照顺序返回ansvector<int> res(2,0);//暴力解题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){res[0] = i;res[1] = j;return res;}}}return res;}
};

下方是哈希表解题：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();//使用target - nums[i]//哈希表，前者入哈希，后者查哈希unordered_map<int,int> hash;for(int i = 0 ; i < n ;i ++){if(hash.find(target - nums[i]) != hash.end()){return {hash[target - nums[i]] , i};}hash[nums[i]] = i;}return {};}
};

141 Linked List Cycle

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {int pos = -1;//哈希表存储什么？unordered_map<ListNode*,int> hash;ListNode *p = head;//一定要全部遍历吗？int i = 0;if(p == nullptr || p->next == nullptr){return false;}//怎么就能判定 p指向了之前的结点while(p){if(hash.find(p) != hash.end()){pos =  hash[p];return true;}hash[p] = i;i++;p = p->next;}return false;}
};

要求空间复杂度为O(1)使用快慢指针。