2Sum_continue

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

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    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: 

    1
2
3
4
5

    Submission Result: Wrong Answer

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

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

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    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: 

    1
2
3
4
5

    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存入呢? 这有点茅塞顿开的意思, 但是悲剧的是依然写错了..

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

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, 按理说不用转换, 不知道为什么, 可能这样更严谨?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;
    }
}

总结: 自己想出来的和之前参考的solution虽然大致思路一样, 但是具体的实现上还是不同的, 而且貌似自己写的更简洁一些. 最后实在找不到问题所在了去看了下之前的solution, 发现那边也是直接map.get( numbers[i]), 并没有加强制类型转换. 不过加上肯定不会错就是了.

LeetCode:TwoSum (1)

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

OJ:

  • 首先用最笨的方法来解，不过好像Java Array的相关method我都忘得差不多了....记录下来再更正吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2]; 
        int l = numbers.size();
        int i, j;
        for (i = 0; i < l; i++){
            for(int j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] = target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}
  • Result: Line4: error: cannot find symbol: method size()

  • 忘记有没有直接看Array长度的函数了，先不去查文档，转化成熟悉的String来做

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        //int l = numbers.size();
        l = source.length();
        int i, j;
        for (i = 0; i < l; i++){
            for(int j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] = target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}

  • Result: Line 6: error: cannot find symbol: variable l 这个错误就是粗心大意了, 后面还有一个错误: Line 9: error: variable j is already defined in method twoSum(int[],int) 我还是再看一遍code再提交吧

  • 审查了一遍,又发现个错误, i的边界判定不应该是length, 而应该是length - 1

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i < l - 1; i++){
            for(j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] = target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}

  • Result: Line 9: error: unexpected type

  • 太不严谨了 - -, 平常用eclipse确实有依赖性, 函数名自己都不去记了, 这种 "==" 自己居然也没注意到

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i < l - 1; i++){
            for(j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
}

  • Result: Line 17: error: missing return statement

  • 简直是错误百出

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i < l - 1; i++){
            for(j = i + 1; j < l; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
        return result;
        
    }
}

  • Result: Runtime Error Message: Line 9: java.lang.ArrayIndexOutOfBoundsException: 3 Last executed input: [3,2,4], 6

  • 再改!

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        int l = source.length();
        int i, j;
        for (i = 0; i <= l - 2; i++){
            for(j = i + 1; j <= l - 1; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i + 1;
                    result[1] = j + 1;
                    return result;
                }
            }
        }
        
        return result;
        
    }
}

  • Result: Runtime Error Message: Line 9: java.lang.ArrayIndexOutOfBoundsException: 3 Last executed input: [3,2,4], 6

  • IMPORTANT: 之所以会这样, 是因为Arrays.toString(), 并不是返回的Arrays里面元素的值, 比如 int[] numbers = {3, 2, 4}, 实测 System.out.println(numbers.toString()) 结果为 [I@53281264 所以上面code中的length实际为11, 怪不得会出现ArrayIndexOutOfBoundsException.

正确获得Arrays长度的方法: Arrays.length

之前刷提的时候不知所以然, 这次我们进阶了, 其实刚才写代码的时候也想到直接用 Arrays.length, 但是这个 .length不是一个method呀, 这在一切皆是Object的Java中显得有些不合群, 所以没用, 这次问题的出现是必然的, 因为我没有系统的学习过数据结构也好, 算法也好, Java也好, 以点带面, 查缺补漏吧.

还是参考StackOverflow的解释: 为什么ArrayList可以用ArrayList.size()来获取ArrayList的长度, 而 Array.length -- 并不是一个method, 却可以得到Array的长度呢?

Arrays are special objects in java, they have a simple attribute named length which is final. There is no "class definition" of an array (you can't find it in any .class file), they're a part of the language itself.

10.7. Array Members

The members of an array type are all of the following: The public final field length, which contains the number of components of the array. length may be positive or zero. The public method clone, which overrides the method of the same name in class Object and throws no checked exceptions. The return type of the clone method of an array type T[] is T[]. A clone of a multidimensional array is shallow, which is to say that it creates only a single new array. Subarrays are shared. All the members inherited from class Object; the only method of Object that is not inherited is its clone method. Note also that ArrayList.size() provides the number of object actually stored in the array whereas myArray.length ([]) provides the "capacity". That is, if for myArray = new int[10];, it returns 10. It is not the number of objects you've put in the array.

  • 改正Arrays.length :

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        String source  = numbers.toString();
        int[] result = new int[2]; 
        // int l = source.length();
        int l = numbers.length;
        int i, j;
        for (i = 0; i <= l - 2; i++){
            for(j = i + 1; j <= l - 1; j++){
                if(numbers[i] + numbers[j] == target){
                    result[0] = i + 1;
                    result[1] = j + 1;
                    return result;
                }
            }
        }
        
        return result;
        
    }
}

  • 改正这一错误之后的代码可以正确运行了, 但是 leetcode的OJ表示此程序太慢了, Time Limit Exceeded.

这并不出乎意料, 因为这个是最笨的方法, 时间复杂度应该是O(n^2)