LeetCode集锦（七） - 第21题 Merge Two Sorted List

发表于 2019-06-07 | 分类于算法 |

问题

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 

 Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4



  public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }

翻译:

合并两个已排序的链表，并将其作为一个新列表返回。新列表应该通过将前两个列表的节点拼接在一起来创建。
例子:
输入:1 - > 2 - > 4,1 - > 3 - > 4
输出:1 - > 1 - > 2 - > 3 - > 4 - > 4
数据格式：
1
2
3
4
5
6
> public class ListNode {
>      int val;
>     ListNode next;
>      ListNode(int x) { val = x; }
> }
>

解题思路

本题思路很简单，就是合并两个链表，通过遍历对方式，逐步把另外一个链合并到新的链里面去，我们这边需要额外到两个节点，一个是头节点，因为在遍历的时候需要保证链头还在，才可以返回数据。还有一个是遍历时，当前节点的前一节点。因为可能会插在前面的节点上。

解题方法

第一种解题方法，我这边使用了l1为基本链，把l2合并到l1中，新建立了链头，这样方便直接插入比l1头部还小的链，代码如下

if (l1 == null) {
        return l2;
    }
    ListNode start = new ListNode(0);
    start.next = l1;
    ListNode before = start;
    while (l1 != null && l2 != null) {
        if (l1.val > l2.val) {
            ListNode temp = l2;
            l2 = l2.next;
            before.next = temp;
            temp.next = l1;
            before = temp;
        } else {
            before = l1;
            l1 = l1.next;
        }
    }
    if (l1 == null) {
        before.next = l2;
    }
    return start.next;

时间复杂度: 该方案用了循环，循环层数为1，循环次数为l1或l2的最小长度，所以T(n)=O(n)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度是O(1);

总结

本题的大致解法如上所诉，本题只想到了一种方法，直接按照思路来。

LeetCode集锦（六） - 第20题 Valid Parentheses

发表于 2019-06-07 | 分类于算法 |

问题

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 

 An input string is valid if: 


 Open brackets must be closed by the same type of brackets. 
 Open brackets must be closed in the correct order. 


 Note that an empty string is also considered valid. 

Example 1: 
    Input: "()"
    Output: true

Example 2: 
    Input: "()[]{}"
    Output: true

Example 3: 
    Input: "(]"
    Output: false

Example 4: 
    Input: "([)]"
    Output: false

Example 5: 
    Input: "{[]}"
    Output: true

翻译:

给定一个只包含字符’(‘，’)’，’{‘，’}’，’[‘和’]’的字符串，判断输入字符串是否有效。
输入字符串在下列情况下有效:

开括号必须由相同类型的括号关闭。

开括号必须按正确的顺序关闭。

注意，空字符串也被认为是有效的。

示例1:
输入:“()”
输出:true
示例2:
输入:“()(){}”
输出:true
示例3:
输入:“()”
输出:false
示例4:
输入:“(())”
输出:false
例5:
输入:“{[]}”
输出:true

解题思路

本题思路很简单，如果左开符号(类似：(,{,[等),那么不管，或者把对应的压入栈，如果遇到右开，则需要判断离他最近的左开符号是否能成对，不能返回失败，如果能则需要去除，避免下一个判断的影响。
这边提供两类思路方案：
方案一：不使用额外空间，只用当前数组，我们遇到右开符号，就要向前进行遍历，遇到第一个不为空的字符，判断是否能成对，如果能则继续，不能返回false。如果最终数组都是空字符串，那么符合要求，返回true，不然返回false。

方案二：使用stack数据结构，把左开符号压入栈中，遇到右开符号，则拿出栈，pop一个，判断是否能成对，如果能则继续，不能返回false，如果最终栈是空的，返回true，否则返回false。

解题方法

第一种解体方法，按照我们的思路来编辑，代码如下

    public boolean isValid(String s) {

    char[] chars = s.toCharArray();

    for (int i = 0; i < chars.length; i++) {
        char indexItem = chars[i];
        char temp = ' ';
        switch (indexItem) {
            case ']':
                temp = '[';
                break;
            case '}':
                temp = '{';
                break;
            case ')':
                temp = '(';
                break;
            default:
                temp = ' ';
        }
        if (temp != ' ' && !find(chars, i, temp)) {
            return false;
        }
    }
    return String.valueOf(chars).trim().length() == 0;
}

private boolean find(char[] chars, int lastIndex, char target) {

    for (int i = lastIndex - 1; i >= 0; i--) {
        char temp = chars[i];
        if (temp == ' ' || temp == ')' || temp == ']' || temp == '}') {
            continue;
        }
        if (chars[i] != target) {
            return false;
        }
        //两者滞空，
        chars[i] = ' ';
        chars[lastIndex] = ' ';
        return true;
    }
    return false;
}

时间复杂度: 该方案用了循环，循环层数为2(算上向前遍历)，由于第二层判断计数不好记，设为M,外层循环为n,所以f(n)=(n*M)=Mn;所以O(f(n))=O(Mn),即T(n)=O(n^2)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度是O(1);

第二种解题方法，按照我们的思路来编辑，代码如下

Stack<Character> stack = new Stack<>();
    int size = s.length();
    for (int i = 0; i < size; i++) {
        char indexChar = s.charAt(i);
        switch (indexChar) {
            case '{':
                stack.push('}');
                break;
            case '[':
                stack.push(']');
                break;
            case '(':
                stack.push(')');
                break;
            default:
                if (stack.size() == 0) {
                    return false;
                } else if (stack.pop() != indexChar) {
                    return false;
                }
        }

    }
    return stack.size() == 0;

时间复杂度: 该方案用了循环，循环层数为1，循环为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)

空间复杂度: 该方案使用栈作为额外，额外的空间最坏的情况就是全部入栈，为n，所以空间复杂度是O(n);

第三种解题方法，按照我们的思路来编辑，代码如下

LinkedList<Character> linkedList=new LinkedList();
    int size = s.length();
    for (int i = 0; i < size; i++) {
        char indexChar = s.charAt(i);
        switch (indexChar) {
            case '{':
                linkedList.addFirst('}');
                break;
            case '[':
                linkedList.addFirst(']');
                break;
            case '(':
                linkedList.addFirst(')');
                break;
            default:
                if (linkedList.size() == 0) {
                    return false;
                } else if (linkedList.getFirst() != indexChar) {
                    return false;
                }
                linkedList.remove(0);
        }

    }

    return linkedList.size() == 0;

时间复杂度: 该方案用了循环，循环层数为1，循环为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)

空间复杂度: 该方案使用链表作为额外，额外的空间最坏的情况就是全部入链表，为n，所以空间复杂度是O(n);

总结

本题的大致解法如上所诉，本题两种思路，三种解题方式，第三种主要是选择的数据结构不同，java自带的Stack是继承Vector，是一个线程安全的，但是在本题不需要考虑安全性，所以加锁的开销是多余的，而且不能一开始就设置Stack的大小，在Vector中使用数组作为存储结构，所以当长度足够长，数组扩容时间和空间损耗会比较大，所以选用LinkedList，没有数组扩容的问题，可以随意增加和删除节点。没有必要线程安全，就没有加锁的额外开销了。

LeetCode集锦（五） - 第14题 Longest Common Prefix

发表于 2019-06-07 | 分类于算法 |

问题

Write a function to find the longest common prefix string amongst an array of strings. 

 If there is no common prefix, return an empty string "". 

 Example 1: 


Input: ["flower","flow","flight"]
Output: "fl"


 Example 2: 


Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.


 Note: 

 All given inputs are in lowercase letters a-z.

翻译:

编写一个函数来查找字符串数组中最长的公共前缀字符串。
如果没有公共前缀，返回一个空字符串“”。
示例1:
输入:[“flower”、“flow”、“flight”)
输出:“fl”
示例2:
输入:“dog”,“racecar”,“car”)
输出:”“
说明:输入字符串之间没有公共前缀。
注意:
所有给定的输入都是小写字母a-z。

解题思路

本题思路很简单，我们选定一个字符串（如果是最短的就最好了），然后根据循环，来一个个对比数组里面的字符串，一个个字符判断，来获取最短路径，找到符合条件的公共字符串，在和下一个比较，最终就是结果了

解题方法

第一种解体方法，按照我们的思路来编辑，代码如下

if (strs.length == 0) {
    return "";
}
if (strs.length == 1) {
    return strs[0];
}

String st = strs[0];
StringBuilder stringBuilder = new StringBuilder("");
for (int i = 0; i < st.length(); i++) {
    char s = st.charAt(i);
    for (int m = 1; m < strs.length; m++) {
        if (strs[m].length() <= i || strs[m].charAt(i) != s) {
            return stringBuilder.toString();
        }
    }
    stringBuilder.append(s);
}
return stringBuilder.toString();

时间复杂度: 该方案用了循环，循环层数为2，由于第二层判断计数不好记，设为M,外层循环为n,所以f(n)=(n*M)=Mn;所以O(f(n))=O(Mn),即T(n)=O(Mn)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度是O(1);

总结

本题的大致解法如上所诉，本题只想到了一种方法，本来想优化查找的，使用二分法来查找，但是想到了二分法的应用场景：更多是用于定位，而不是圈定范围，所以就放弃了这个想法。

LeetCode集锦（四） - 第13题 Roman To Integer

发表于 2019-06-07 | 分类于算法 |

问题

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. 

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000 

 For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II. 

 Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used: 

 I can be placed before V (5) and X (10) to make 4 and 9. 
 X can be placed before L (50) and C (100) to make 40 and 90. 
 C can be placed before D (500) and M (1000) to make 400 and 900. 

 Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. 

 Example 1: 

Input: "III"
Output: 3 

 Example 2: 

Input: "IV"
Output: 4 

 Example 3: 

Input: "IX"
Output: 9 

 Example 4: 

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

 Example 5: 

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

翻译:

罗马数字由七种不同的符号表示:I、V、X、L、C、D和M。
符号的值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，2用罗马数字写成II，两个1相加。12写成，XII，就是X + II。27被写成XXVII，也就是XX + V + II。
罗马数字通常从左到右由大到小书写。然而，4的数字不是IIII。4写成了4，因为1在5之前，所以减4。同样的原理也适用于数字9，也就是9。减法有六种应用:

I可以把V(5)和X(10)放在前面，得到4和9。

X可以放在L(50)和C(100)之前，得到40和90。

C可以放在D(500)和M(1000)之前，得到400和900。

给定一个罗马数字，把它转换成整数。输入保证在1到3999之间。
示例1:
输入:“III”
输出:3
示例2:
输入:“IV”
输出:4
示例3:
输入:“IX”
输出:9
示例4:
输入:“LVIII”
输出:58
说明:L = 50, V= 5, III = 3。
例5:
输入:“MCMXCIV”
输出:1994
说明:M = 1000, CM = 900, XC = 90, IV = 4。

解题思路

罗马数字的定义：维基百科
在维基百科中，有条对我们本题解题很有帮助的一个规律，为：右加左减

在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。

所以本题的思路就很清楚，我们从不遵从特性到遵从特性的情况逐步分析，可以分为3个思路:

思路一：直接按照字面来解决，我们可以先把罗马数字的含义记录到map，方便我们获取，包括特殊情况：”IV”等这类,然后循环获取字符，如果是’I’,’X’,’C’我们就获取下一个字符，看看能否组合成特殊的情况，如果组合成功，则加上值，并下标移动，如果失败，加上本身的值。其他情况则加上本身的值就ok了。

思路二：该思路是对思路一的一种改进，我们知道特殊情况都是由前一个和当前这个组成（当然也可以是当前这个和后一个符号组合，相比是前后方便一点，因为思路一其实就是前后判断），所以我们主要记录前一个字符，和当前字符能否组合成特殊字符，如果能，减去前一字符两倍的值。最终都是加上当前的值。

思路三：该思路是使用了上文提到的规律，如果左边的数小于右边的数，那么操作减法，相反则是加法。所以我们只需要判断前后大小，按照对应的计算方式，就可以算出值。

解题方法

第一种解体方法，按照我们的思路来编辑，代码如下

Map<String, Integer> map = new HashMap<>(16);
    map.put("I", 1);
    map.put("V", 5);
    map.put("IV", 4);
    map.put("IX", 9);
    map.put("X", 10);
    map.put("XL", 40);
    map.put("L", 50);
    map.put("XC", 90);
    map.put("C", 100);
    map.put("CD", 400);
    map.put("D", 500);
    map.put("CM", 900);
    map.put("M", 1000);

    int result = 0;
    for (int i = 0; i < s.length(); i++) {

        char c = s.charAt(i);
        String temp = String.valueOf(c);
        if ((c == 'I' || c == 'X' || c == 'C') && (i + 1) < s.length()) {
            String m = String.valueOf(new char[]{c, s.charAt(i + 1)});
            if (map.get(m) != null) {
                temp = m;
                i++;
            }
        }
        result += map.get(temp);

    }
    return result;

时间复杂度: 该方案用了循环，循环层数为一，所以记为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)

空间复杂度: 该方案使用了map存储罗马数值和阿拉伯数值的基本关系，是额外空间，不算空间复杂度，所以空间复杂度是O(1);

第二种解题方法，代码如下:

Map<String, Integer> map = new HashMap<>(7);
   map.put("I", 1);
   map.put("V", 5);
   map.put("IV", 4);
   map.put("IX", 9);
   map.put("X", 10);
   map.put("XL", 40);
   map.put("L", 50);
   map.put("XC", 90);
   map.put("C", 100);
   map.put("CD", 400);
   map.put("D", 500);
   map.put("CM", 900);
   map.put("M", 1000);

   char last = s.charAt(0);
   int result = map.get(String.valueOf(last));

   for (int i = 1; i < s.length(); i++) {
       char c = s.charAt(i);
       String temp = String.valueOf(new char[]{last, c});
       Integer integer = map.get(temp);
       if (integer != null) {
           result = result - 2 * map.get(String.valueOf(last));
       }
       result += map.get(String.valueOf(c));
       last = c;
   }
   return result;

时间复杂度: 该方案用了循环，循环层数为一，所以记为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)

空间复杂度: 该方案使用了map存储罗马数值和阿拉伯数值的基本关系，是额外空间，不算空间复杂度，所以空间复杂度是O(1);

第三种解题方法，代码如下:

Map<Character, Integer> map = new HashMap<>(7);
    map.put('I', 1);
    map.put('V', 5);
    map.put('X', 10);
    map.put('L', 50);
    map.put('C', 100);
    map.put('D', 500);
    map.put('M', 1000);

    char last = s.charAt(0);
    int result = map.get(last);

    for (int i = 1; i < s.length(); i++) {
        char c = s.charAt(i);

        if (map.get(last) < map.get(c)) {
            result = result - 2 * map.get(last);
        }
        result += map.get(c);
        last = c;
    }
    return result;

时间复杂度: 该方案用了循环，循环层数为一，所以记为n,所以f(n)=(n)=n;所以O(f(n))=O(n),即T(n)=O(n)

空间复杂度: 该方案使用了map存储罗马数值和阿拉伯数值的基本关系，是额外空间，不算空间复杂度，所以空间复杂度是O(1);

总结

本题的大致解法如上所诉，方案1和2因为要存储多余字符，所以只能用字符串类型存储，这就导致了后续字符都要转成字符串，出现了额外的开销，这个还是比较痛苦的，相对方案3就直接存储了字符，直接取就ok了。

LeetCode集锦（三） - 第9题 Palindrome Number

发表于 2019-06-07 | 分类于算法 |

问题

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. 
 Example 1: 

Input: 121
Output: true

 Example 2: 

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

 Example 3: 

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

 Follow up: 

 Coud you solve it without converting the integer to a string?

翻译:

确定整数是否是回文。当一个整数向后读取与向前读取相同的内容时，它就是一个回文。
示例1:
输入:121
输出:真正的
示例2:
输入:-121
输出:假
说明:从左到右，是-121。从右到左，变成121-。因此它不是回文。
示例3:
输入:10
输出:假
说明:从右向左读取01。因此它不是回文。
跟进:
你能在不把整数转换成字符串的情况下解出它吗?

解题思路

本题目标是判断一个数字是不是回文数字。

回文数字的定义：翻转数字后，和本身一样则为回文数字。

根据回文数字的定义，负数是不符合要求的，毕竟符号的限制存在，个位数一定是回文数字。

在定义中，是需要翻转数字，判断前后是否一致，很容易想到可以转化为String，然后翻转一下，是否一致就可以。

还有一种方式，就是一位位的取，重新组装数字，判断是否一致，但是这样需要避免溢出的问题。

解题方法

第一种解体方法，按照我们的思路来编辑，代码如下

//负数直接不符合要求
   if (x < 0) {
       return false;
   }
   StringBuilder stringBuilder = new StringBuilder(x + "");
   return stringBuilder.toString().equals(stringBuilder.reverse().toString());

时间复杂度: 该方案用了并没有使用循环，其实在翻转过程中应该是用来循环，但是这边不计算，所以f(n)=1=1;所以O(f(n))=O(1),即T(n)=O(1)

空间复杂度: 该方案使用了StringBuilder,相当于复刻了一个数组，所以空间复杂度是O(1);

第二种解题方法，代码如下:

//负数直接不符合要求
    if (x < 0) {
        return false;
    }
    int temp = x;
    long result = 0;
    while (temp != 0) {
        long remainder = temp % 10;
        result = result * 10 + remainder;
        temp /= 10;
    }
    return result == x;

时间复杂度: 该方案用了单层循环,所以f(n)=(log10(n)+1)/2=log10(n)/2;所以O(f(n))=O(log10(n))=O(log10(n)),即T(n)=O(log10(n))

空间复杂度: 该方案并没有使用额外的空间在存储数值，所以为O(1);

总结

本题的大致解法如上所诉，方案2没有利用到字符串，直接由本身出发，空间和时间上都比方案一快,唯一一点是需要用long来控制，避免越界。

LeetCode集锦（二） - reverse integer

发表于 2019-06-07 | 分类于算法 |

问题

Given a 32-bit signed integer, reverse digits of an integer. 
Example 1: 
Input: 123
Output: 321
 Example 2: 
Input: -123
Output: -321
 Example 3: 
Input: 120
Output: 21


 Note: 
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

翻译:

给定一个32位带符号整数，对其进行反数运算。
示例1:
输入:123
输出:321
示例2:
输入:-123
输出:-321
示例3:
输入:120
输出:21
注意:
假设我们处理的环境只能存储32位带符号整数范围内的整数:[- 231,231 - 1]。对于这个问题，假设函数在反向整数溢出时返回0。

解题思路

本题字面含义其实是对一个整数进行反转，这边需要注意三个点：

带符号
32位数字，反转后可能会溢出
翻转后开头为0的要去掉。

思路一：我们可以利用String来进行直接的反转，对目标数先取绝对值，然后翻转，然后去掉头部为0的数字，并且反转完后把符号带上，如果大于Integer，则返回0，这边可以用long来代替，或者在转化integer的时候进行异常捕获

思路二：直接进行数字的翻转，先取绝对值，一个个位数获取下来，然后在拼接为最终结果，并除去头部为0的值，最后赋予富豪，用long来代替，比较integer的最大值。

解题方法

第一种解体方法，按照我们的思路来编辑，代码如下

//首先把0特殊去掉
   if (x == 0) {
       return 0;
   }
   //如果是负数，则变化成正数
   int temp = x;
   boolean isMinus = false;
   if (x < 0) {
       temp = -temp;
       isMinus = true;
   }
   //翻转,
   StringBuilder stringBuilder = new StringBuilder(temp+"").reverse();
   //除去前面的0
   int zoreCount = 0;
   for (int i = 0; i < stringBuilder.length(); i++) {
       if (stringBuilder.charAt(i) == '0') {
           zoreCount++;
       } else {
           break;

       }
   }
   if(zoreCount>0){
       stringBuilder.delete(0,zoreCount);
   }
   try{
       return Integer.valueOf(isMinus?"-"+stringBuilder.toString():stringBuilder.toString());
   }catch (Exception e){
       return 0;
   }

时间复杂度: 该方案用了并没有使用循环，其实在翻转过程中应该是用来循环，但是这边不计算，这边在判断头部为0的情况下，循环来一次，所以记为n,所以f(n)=((log10(n)-1)+0)/2=log10(n)/2;所以O(f(n))=O(log10(n)),即T(log10(n))=O(n)

空间复杂度: 该方案使用了StringBuilder,相当于复刻了一个数组，所以空间复杂度是O(1);

第二种解题方法，代码如下:

//如果是负数，则变化成正数
   long temp = x;
   boolean isMinus = false;
   if (x < 0) {
       temp = -temp;
       isMinus = true;
   }
   long value = 0;
   //获取长度。
   while (temp / 10 != 0 || temp % 10 != 0) {
       long remainder = temp % 10;

       value = value * 10 + remainder;
       if (value > Integer.MAX_VALUE) {
           return 0;
       }

       temp = temp / 10;
   }

   return (int) value * (isMinus ? -1 : 1);

时间复杂度: 该方案用了单层循环,所以f(n)=(log10(n)+1)/2=log10(n)/2;所以O(f(n))=O(log10(n))=O(log10(n)),即T(n)=O(log10(n))

空间复杂度: 该方案并没有使用额外的空间在存储数值，所以为O(1);

总结

本题的大致解法如上所诉，方案2没有利用到字符串，直接由本身出发，空间和时间上都比方案一快,唯一一点是需要用long来控制，万一int是负数最小值，一旦变成正数，就溢出了。

LeetCode集锦（一） - two sum

发表于 2019-06-07 | 分类于算法 |

问题

Given an array of integers, return indices of the two numbers such that they add up to a specific target. 

 You may assume that each input would have exactly one solution, and you may not use the same element twice. 

 Example: 


Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻译:

给定一个整数数组，返回两个数字的索引，使它们加起来等于一个特定的目标。

您可以假设每个输入都只有一个解决方案，并且不能两次使用相同的元素。

给定数组:[2, 7, 11, 15] ,两数和为:9

因为按顺序而言，2+7等于9，所以选择2和7对应的下标，0，1构成新数组。返回结果为[0,1]

解题思路

本题字面含义其实是求和，找寻两个数字的和为目标值，然后输出该两个数字的下标值。

换一个角度而言，我们这边有一个最终结果值–目标值，和一系列待选值–数组，如果我们在待选值中选择一个值，由目标值减去改值，就是另外需要寻找的值。这样我们就拿到全部需要的结果，需要做的只是从待选值中，查找那个差值。

解题方法

第一种解体方法，按照我们的思路来编辑，代码如下

for (int i = 0; i < nums.length; i++) {
    int differ = target - nums[i];

    for (int m = i + 1; m < nums.length; m++) {
        if (differ == nums[m]) {
            return new int[]{i, m};
        }
    }
}
return new int[]{};

时间复杂度: 该方案用了两层嵌套循环，第一层循环度为n，第二层循环度也是n-m,所以f(n)=n*(n-m)=n^2-mn;所以O(f(n))=O(n^2),即T(n)=O(n^2)

空间复杂度: 该方案并没有使用额外度空间去存储，所以空间复杂度还是O(1);

第二种解题方法，是延伸出来，既然我们要寻找另外一个值，是否可以用map这类数据结构来方便查询呢？代码如下:

//先转化为hashmap
Map<Integer, Integer> map = new HashMap<>(nums.length);
for (int i = 0; i < nums.length; i++) {
    map.put(nums[i], i);
}

for (int i = 0; i < nums.length; i++) {
    Integer integer = map.get(target - nums[i]);
    //如果是本身，就跳过
    if (integer != null && integer!=i) {
        return new int[]{i, integer};
    }
}
return new int[]{};

时间复杂度: 该方案用了单层循环，两次单层循环,所以f(n)=n+n=2n;所以O(f(n))=O(2n)=O(n),即T(n)=O(n)

空间复杂度: 该方案使用了HashMap去存储数值和索引的关系，所以是原来数组的近似2倍（这边不考虑因为数据结构而导致的开销),即为2n,所以总共的空间复杂度为O(f(n))=O(3n)=O(n),所以空间复杂度还是O(n);

第三种解题方案是针对与第二种解题优化的，第二种方案是直接把数组转化为map，所以这部分的空间开销是固定，如果我们可以一边读取，一边储存，那么是否可以更加简单呢？因为9-2=7，相对的9-7=2。所以按照这种思路，出现了第三种解题方案,代码如下:

Map<Integer, Integer> map = new HashMap<>(nums.length);
for (int i = 0; i < nums.length; i++) {
   int differ = target - nums[i];
   Integer result = map.get(differ);
   if (null != result) {
      return new int[]{result,i };
   }
   map.put(nums[i], i);
}
return new int[]{};

总结

本题的大致解法如上所诉，但是可以更改的方式很多，如果输入的数组出现重复的情况，那么方法2是一个致命的错误解法，因为会把它覆盖，所以个人觉得，方法三是相对较优的一种解法。

FightCrap

制造bug的永动机

GitHub E-Mail