2019-05-10

1. Two Sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] + nums[j] == target){
                    ans.push_back(i);
                    ans.push_back(j);
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for(int i = 0; i < nums.size(); i++){
            int complement = target - nums[i];
            if(map.find(complement) != map.end()){
                return {map[complement], i};
            }
            map[nums[i]] = i;
        }
        return {};
    }
};

unordered_map<int, int> map;

map 与 unordered_map 的区别

map: map 内部实现了一个红黑树，该结构具有自动排序的功能，因此 map 内部的所有元素都是有序的，红黑树的每一个节点都代表着 map 的一个元素，因此，对于 map 进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了 map 的效率。

unordered_map: unordered_map 内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        
        dummy->next = head;
        
        int length = 0;
        
        ListNode* first = head;
        
        while(first){
            length++;
            first = first->next;
        }
        
        length -= n;
        
        first = dummy;
        
        while(length > 0){
            length--;
            first = first->next;
        }
        
        first->next = first->next->next;
        
        return dummy->next;
    }
};