Jamzen的技术博客
0%

LeetCode-两数之和

发表于 分类于 Valine：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

  • 示例:
    给定 nums = [2, 7, 11, 15], target = 9
  • 因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

    1. 蛮力法：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /**
     * 暴力解法, 时间复杂度O(n^2)
     **/
    def solution(nums: Array[Int], target: Int): Array[Int] = {
         if (nums == null || nums.length < 2) {
              return Array(-1, -1)
         }

         for (i <- 0 until nums.length) {
              for (j <- i + 1 until nums.length) {
                   if (nums(i) + nums(j) == target) {
                        return Array(i, j)
                   }
              }
         }
         Array(-1, -1)
    }

2. Hash思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * hash表, 时间复杂度O(2n)
 */
def solution2(nums: Array[Int], target: Int): Array[Int] = {
     if (nums == null || nums.length < 2) {
          return Array(-1, -1)
     }

     val map = mutable.Map[Int, Int]()
     for (i <- 0 until nums.length) {
          map += (nums(i) -> i)
     }

     for (i <- 0 until nums.length) {
          //hash 判断不需要遍历n次，hash的时间复杂度为1
          if (map.contains(target - nums(i)) && i != map.get(target - nums(i)).get) {
               return Array(i, map.get(target - nums(i)).get)
          }
     }

     Array(-1, -1)
}

3. Hash思想,一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * hash表，一次遍历, 时间复杂度O(n)
 */
def solution3(nums: Array[Int], target: Int): Array[Int] = {
     if (nums == null || nums.length < 2) {
          return Array(-1, -1)
     }

     val map = mutable.Map[Int, Int]()

     for (i <- 0 until nums.length) {
          //hash 判断不需要遍历n次，hash的时间复杂度为1
          val left = target - nums(i)
          if (map.contains(left)) {
               if (i != map.get(left).get) {
                    return Array(i, map.get(left).get)
               }
          } else {
               map += (nums(i) -> i)
          }
     }

     Array(-1, -1)
}