Topic describes

Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts. You can assume that there is only one answer for each type of input. However, you cannot reuse the same elements in this array. Example: Given nums = [2, 7, 11, 15], target = 9Copy the code

1. CPP violence solution

Because there is only one target in the array, a double loop is performed directly, with I and j being the subscripts of the two numbers. Return {} is C++ 11 and returns a vector.

Time complexity: O(n^2^).

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

2. Use CPP Map

Answer:

  • Use hash table to record the occurrence of the numeric subscript, save the query time.
  • When a + b == target, a == target – b.
  • If a == target-b exists in the hash table, return the subscripts of a and b.
  • Vector has list initials. return {index_of_A, index_of_B} reduces code length.

First, create an unsorted map, then iterate through the number group, using dict.count to count the number of keys:

  • If 0 is returned, there is no match yet, and dict[nums[I]] is assigned to I.
  • If there is a match, return target-nums [I] and the dictionary subscript of I.

Dict [target-nums [I]] is the index for finding numbers, and I is the index for traversing numbers.

Time complexity: O(n). You just have to go through the array once

class Solution {
public:
    vector<int> twoSum(const vector<int>& nums, const int target) {
        unordered_map<int, int> dict;
        for(int i = 0; i < nums.size(); I++) //dict.count can also use dict.find()if (dict.count(target - nums[i]))
                return {dict[target - nums[i]], i};
            elsedict[nums[i]] = i; // If you can't find itreturn{0, 0}; }};Copy the code

Unordered_map is an associative container in which elements are referenced by key rather than index. To use it, you must include unordered_map. Internally, elements in STD :: Unordered_map are not ordered in any particular order based on their key value or mapped value, but are organized into buckets based on their hash value to allow quick access to individual elements directly via their key value (average time complexity of constants). Also, the keys of elements in STD ::unorederd_map are unique.

Java Map (same as 2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution"); }}Copy the code

Return new int[] {map.get(complement), I}; Is similar to an anonymous function that returns an array object

Python Dict (dict)

class Solution(object):
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        dict = {}

        for i in range(0,len(nums)):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            dict[target - nums[i]] = i

        return [0, 0]
Copy the code

Time complexity of each language and algorithm