LeetCode Two Sum 及C++map浅显理解

1
2
3
4
5
6
7
8
9
10
11
12
for (int i=0; i<numbers.size(); ++i)
{
    for (int j=i+1; j<numbers.size(); ++j)
    {
        if (numbers[i] + numbers[j] == target)
        {
            a = i;
            b = j;
            break;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Node{
  public:
    int value;//用来保存数组的值
    int key;  //用来保存对应值所对应的下标
};

bool cmp(Node a, Node b)
{
    return a.value < b.value; //排序函数所需谓词，从小到大进行排序
}
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int i, sum;
        vector<int> results;             //用来保存结果
        vector<Node> arry;               
        for (i=0; i<numbers.size(); ++i) //这一步就是将数组numbers所有的值及相对应的下标存进去
        {
            Node *tmp = new Node;
            tmp->value = numbers[i];
            tmp->key = i+1;
            arry.push_back(*tmp);
        }
        sort(arry.begin(),arry.end(),cmp); //对arry按照值的大小从小到大进行排序

        vector<Node>::iterator j = arry.begin();
        vector<Node>::iterator k = arry.end()-1;
        sum = 0;
        /*
        这一部分很简单，其实就是对已经排序好的arry从两头开始
        进行查找，若sum小于target，很明显需要将j往后移位，若sum
        大于target，很明显需要将k往前移位，直到找到sum==target
        */
        while (j < k)                 
        {                             
            sum = j->value + k->value;
            if (sum > target) --k;    
            else if (sum < target) ++j;
            else
            {
                int temp;
                if (j->key > k->key)//考虑到数组中有负数的原因，会因为排序后而发生j->key > k->key 的现象，需要调换
                {
                    temp = j->key;
                    j->key = k->key;
                    k->key = temp;
                }
                results.push_back(j->key);
                results.push_back(k->key);
                break;
            }
        }

        return results;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int i, sum;
        vector<int> results;
        map<int, int> hmap;
        for(i=0; i<numbers.size(); i++){
            if(!hmap.count(numbers[i])){
                hmap.insert(pair<int, int>(numbers[i], i));
            }
            if(hmap.count(target-numbers[i])){
                int n=hmap[target-numbers[i]];
                if(n<i){
                    results.push_back(n+1);
                    results.push_back(i+1);

                    return results;
                }

            }
        }
        return results;
    }
};

1
2
3
if(!hmap.count(numbers[i])){
                hmap.insert(pair<int, int>(numbers[i], i));
            }