arithmetic

1. Two Sum

Posted by Jfson on 2017-12-15
  • 1.题目(LeetCode | 1 | easy)：
1
2
3
4
5
6
7
8
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:
1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
  • 解：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            for(int i = 0;i<nums.length;i++){
                for(int j = i+1;j<nums.length;j++){
                    if(nums[j] == target - nums[i]){
                        return new int[]{i,j};
                    }
                }
            }
            throw new IllegalArgumentException("No find sum");
        }
    }

总结

  • 手生。很简单的一道题。好几次才解开。

    • 第一次 int 没有声明
    • 第二次 for 中“;” 写成 “，”
    • 第三次 if 中赋值用“==”，错写成了“=”
    • IllegalArgumentException 不会拼写

  • 复杂度分析欠缺，先贴上来，后续补

  • 复杂性分析

    • 时间复杂度： 为O（n ^ 2）ø （Ñ
      2
      ）。对于每个元素，我们试图通过循环其余的数组来找到它的补码上）O （n ）时间。所以时间复杂度是为O（n ^ 2）ø （Ñ
      2
      ）。

    • 空间复杂性： O（1）O （1 ）。

FEATURED TAGS
arithmetic
pv UV: