Mar 20 2014

2Sum_continue

凭着记忆写一下hashmap的写法:

其实已经是修改过几个小毛病的版本, 比如new HashMap;

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        int j = numbers.length - 1;
        while(i <= j){
            if(!map.containsKey(numbers[j])){
                map.put(target - numbers[i], numbers[i]);
                i++;
                j--;
            }else{
                result[0] = i + 1;
                result[1] = j + 1;
                return result;
            }
        }
        
        return result;
    }
}

Result:

Submission Result: Wrong Answer

Input:	[3,2,4], 6
Output:	0, 0
Expected:	2, 3

调整一下i和j的变更条件:

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        int j = numbers.length - 1;
        while(i <= j){
            while(j > 0){
                if(!map.containsKey(numbers[j])){
                    map.put(target - numbers[i], numbers[i]);
                    i++;
                }else{
                    result[0] = i + 1;
                    result[1] = j + 1;
                    return result;
                }
                j--;
            }
        }
        
        return result;
    }
}

Result:

Submission Result: Wrong Answer

Input:	[3,2,4], 6
Output:	0, 0
Expected:	2, 3

分析: 理论上之前本方法的时间复杂度是O(n^2); 如果按照上面写法两个while循环钱淘的话, 依然还是O(n^2), 这样就没意义了, 应该扫一遍数据进hashtable就可以判断出是否有结果了, 上面的问题就是怎样在得到两个相加和为target的数值之后取得他们的index,

何不在扫入hashmap的时候把index作为value存入呢? 这有点茅塞顿开的意思, 但是悲剧的是依然写错了..

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        int j = 0;
        while(i < numbers.length){
            if(!map.containsKey(numbers[i])){
                map.put(target - numbers[i], i);
                i++;
            }else{
                j = map.get(target - numbers[i]);
                if(i < map.get(target - numbers[i])){
                    result[0] = i + 1;
                    result[1] = map.get(target - numbers[i] + 1);
                    return result;
                }else{ 
                    result[0] = j + 1;
                    result[1] = i + 1;
                    return result;
                }
            }
        }
        return result;
    }
}

Result:

1
2
3

Submission Result: Compile Error

Line 12: error: incompatible types

借助于eclipse debug, 终于找到问题所在, 应该去get(numbers[i]), 另外不加(Integer) leetcode无法贬编译 + 这个运算符, 其实我已经定义了get出来的是Integer, 按理说不用转换, 不知道为什么, 可能这样更严谨?

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map map = new HashMap<Integer, Integer>();
        int i = 0;
        while(i < numbers.length){
            if(!map.containsKey(numbers[i])){
                map.put(target - numbers[i], i);
                i++;
            }else{
                result[0] = (Integer)map.get( numbers[i]) + 1;
                result[1] = i + 1;
                return result;
            }

        }
        return result;
    }
}