Start by swiping Leetcode

  1. Given an array of integers and a target value, find two numbers that neutralize the target value in the array. You can assume that there is only one answer for each input and that the same elements cannot be reused. Example: Given nums = [2, 7, 11, 15], target = 9

1. Violent traversal, traversal each element x, and then find whether there is a target value of -x value, if there is, return. Time complexity O(n2), space complexity O(1). 2. The time complexity of using the hash table to search is O(1). Iterate over each element again to see if there is a value in the hash table. Time complexity O(n2), space complexity O(n). 3. After traversing twice, it can be optimized to once. If there is a direct return, no, save again.

The algorithm is as follows:

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 differ = target - nums[i];
            auto result  = map.find(nums[i]);
            if(result ! = map.end()) {return {result->second,i};
            }
            else{ map[differ] = i; }}return{}; }};Copy the code

Using C++11’s unordered_map further improves the efficiency of the algorithm

  1. Add two numbers Given two non-empty linked lists to represent two non-negative integers. The digits are stored in reverse order, with each node storing only a single digit. Adding the two numbers returns a new linked list. You can assume that neither of these numbers will start with zero, except for the number zero. Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Cause: 342 + 465 = 807

Initialize a new list Result. Traverse two non-empty linked lists synchronously using a single pointer. Use temporary flag bits to indicate carry. Each iteration expands the Result list by a node with that value, and adds the carry value to the sum.

The algorithm is implemented as follows

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        struct ListNode* res = new ListNode(0);
        struct ListNode* current = res;
        
        int carry = 0;
        
        while (l1 || l2) {
            int sum = carry;
            if(l1 ! = NULL) { sum += l1->val; l1 = l1->next; }if(l2 ! = NULL) { sum += l2->val; l2 = l2->next; } current->val = sum%10; carry = sum/10;if (l1 || l2 || carry!= 0) {
                current->next = new ListNode(0);
                current = current->next;
            }
        }
        if(carry ! = 0) { current->val = carry; }returnres; }};Copy the code

Note that 1: the given two lists have different lengths, and 2: there will eventually be a carry

Time complexity: O(Max (m,n)); Space complexity :O(Max (m,n))+1;