Leetcode / Scala - sum of two numbers, three numbers, four numbers, and N numbers

One . introduction

LeetCode There are   Sum of two numbers , Sum of three numbers , Sum of four numbers , The main implementation method is Python,Java,C++, Use scala respectively , And deduce N Implementation method of sum of numbers .

Two . Sum of two numbers

1. Subject requirements

Given array nums and target, Returns the subscript i、j Satisfy nums[i] + nums[j] = target, Note here that there will only be one valid answer .

2. Violent cycle

A. Thought analysis

Start two directly For loop , To traverse separately nums Elements of array , If meet nums[i] + nums[j] = target And i != j, It means that the result is found .

B. Code implementation

  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    nums.indices.foreach(i => { //  Traverse every element of the array 
      nums.indices.foreach(j => { //  Traverse every element of the array 
        if (nums(i) + nums(j) == target && i != j) { //  duplicate removal 
          return Array(i, j)
        }
      })
    })
    null
  }

C. Execution efficiency

Through all the examples in the simplest way , But the execution time is touching .

3. HashMap Clear version

A. Thought analysis

Can pass HashMap Storage nums Index of numbers in , Just go through it once nums Array , If num and target - num All in HashMap Of key in , Then return to num and target - num The corresponding index index.

Tips:

scala Can pass zipWithIndex Realization nums Array and index index Corresponding , I first used it directly toMap, But there's a problem , That is, if nums There is the same num Will cause index Overwrite and lose , So there is a special case excluding the equality of two numbers .

B. Code implementation

  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val result = new Array[Int](2) //  Store results 
    val indexMap = new mutable.HashMap[Int, Int]() //  Storage mapping relationship 

    //  Store numbers and indexes 
    nums.zipWithIndex.foreach(kv => {
      if (!indexMap.contains(kv._1)) {
        indexMap(kv._1) = kv._2
      } else {
        if (kv._1 * 2 == target) { //  Exclude the special case that two numbers are equal 
          result(0) = indexMap(kv._1)
          result(1) = kv._2
          return result
        }
      }
    })

    //  By judgment  num  And  target - num  Whether all exist and  indexMap
    nums.foreach(num => {
      val otherNum = target - num
      if (indexMap.contains(otherNum) && num != otherNum) {
        result(0) = indexMap(num)
        result(1) = indexMap(otherNum)
        return result
      }
    })
    result
  }

C. Execution efficiency

  Use HashMap Instead of For Cycle space for time , Too much memory , The running speed is too slow .

4.HashMap Simplified edition

A. Optimization analysis

I'll take a look at the above code , Here, sort out the optimization points ：

· There was only one result , No need to initialize in advance , Save memory

· No need to store separately , You can judge while storing , Save time and space

· At the same time judge num And target - num Shorten the time

Time complexity O(N)- Traverse nums Array , Spatial complexity O(N) - Storage HashMap

B. Code implementation

  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val indexMap = new mutable.HashMap[Int, Int]()

    var index = 0 //  Cumulative index 

    nums.foreach(num => {
      //  Judge  target - num  Whether it also exists with  map
      val flag: Int = indexMap.getOrElse(target - num, -1)

      if (flag != -1) {
        return Array(index, flag)
      }
      indexMap(num) = index //  Save mapping 
      index += 1
    })

    null
  }

C. Execution efficiency

5. Double pointer version

A. Thought analysis

First, sort the array to get an ordered array , Then pointer index left =  0 And rigth = nums.length - 1, Judge sum = nums[left] + nums[right] And target Size , If sum > target Will right - 1, If sum < target be left + 1, To be equal is to pass Array.indexOf Get the index of the corresponding element index.

B. Code implementation

  def twoSum(nums: Array[Int], target: Int): Array[Int] = {

    //  Array sorting 
    val sortedNums = nums.sorted

    //  Judge the repetition 
    val mid = target / 2
    if (nums.contains(mid)) {
      val re = nums.zipWithIndex.filter(_._1.equals(mid)).map(_._2)
      if (re.length > 1) {
        return re
      }
    }

    //  Double pointer traversal 
    var left = 0
    var right = sortedNums.length - 1

    while (left < right) {

      val sum = sortedNums(left) + sortedNums(right)

      if (sum == target) {
        // indexOf  Get element index 
        return Array(nums.indexOf(sortedNums(left)), nums.indexOf(sortedNums(right)))
      } else if (sum > target) {
        right -= 1
      } else {
        left += 1
      }

    }

    null
  }

C. Execution efficiency

Due to the need to consider the situation of weight removal, the execution time is delayed . Here we mainly introduce the idea of double pointer , The sum of the following three numbers , The sum of four numbers needs double pointers to solve .

3、 ... and . Sum of three numbers

1. Subject requirements

It is basically similar to the sum of two numbers , The difference is that this example returns a number instead of a subscript , Secondly, the answer here may not be unique .

2. Double pointer version

A. Thought analysis

The most brainless must be three For loop , And then determine a + b + c =  0, I won't do that here , Let's talk directly about the idea of three pointers ：

-> Sort the array to get an ordered array

-> The element that fixes the first position is start, If the location element is greater than 0 Then exit the loop , Because the array is ordered and requires a sum of 0

-> Regulations left = start + 1,right = nums.length - 1,sum = nums(start) + nums(left) + nums(right)

sum > 0, It's too big ,right - 1

sum < 0, Is too small ,left + 1

sum = 0, take  nums(start) 、nums(left) 、nums(right) Three numbers are added to the candidate set

Tips:

Because the above questions require no repeated solutions , So pay attention to judgment start and start - 1 Are the elements the same , Then analyze the algorithm complexity , Time complexity O(n^2), Array sorting O(N*logN), Traversal array 、 Double pointer O(N), Spatial complexity O(1)

B. Implementation code

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks.{break, breakable}

object Solution {
    def threeSum(nums: Array[Int]): List[List[Int]] = {
    //  Abnormal judgement 
    val length = nums.length
    if (length < 3 || nums.isEmpty) {
      return null
    }

    val sortedNums = nums.sorted //  Array sorting 

    val result = new ArrayBuffer[List[Int]]()

    sortedNums.indices.foreach(index => {


      breakable {

        //  Current number is greater than 0, Then the sum of the following numbers cannot be 0
        if (sortedNums(index) > 0) {
          return result.toList
        }

        //  Exclude outliers 
        if (index > 0 && sortedNums(index) == sortedNums(index - 1)) break()

        var left = index + 1
        var right = length - 1

        while (left < right) {

          val sumValue = sortedNums(index) + sortedNums(left) + sortedNums(right)

          //  Exclude duplicate values 
          if (index > 0 && sortedNums(index) == sortedNums(index - 1)) {
            left = index + 1
            right = length - 1
            break()
          }

          if (sumValue.equals(0)) {
            result.append(Array(sortedNums(index), sortedNums(left), sortedNums(right)).toList)

            while (left < right && sortedNums(left) == sortedNums(left + 1)) {
              left += 1
            }

            while (left < right && sortedNums(right) == sortedNums(right - 1)) {
              right -= 1
            }

            left += 1
            right -= 1

          } else if (sumValue > 0) {
            right -= 1
          } else {
            left += 1
          }
        }
      }



    })

    result.toList
    }
}

C. Execution efficiency

because scala Not supported by default break and continue, So it needs to be imported manually  scala.util.control.Breaks.{break, breakable} Two classes assist in the implementation break and continue Methods .

Four . Sum of four numbers

1. Subject requirements

Except for the sum of three numbers , The official actually gave a sum of four , This time, it changes from numeric value to return index , And ask for a、b、c、d Each are not identical .

2. Double pointer

A. Thought analysis

Add three numbers by fixing the first position start, Then double pointer traversal method , Here expand to fix the first two positions i,j, First, order the array , Need to meet j > i, then left = j + 1,right = nums.length - 1, Subsequent judgment sum = nums(i) + nums(j) + nums(left) + nums(right) And target The relationship between , Too big right -1 , Too small left + 1, Step by step judgment , Cycle once and then accumulate i or j, Continue to cycle .

Tips：

Time complexity : Array sorting O(NLogN), Traverse the first O(N), Traverse the second bit O(N), Double pointer O(N) whole O(N^3)

B. Code implementation

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks.{break, breakable}


object FourNum_18 {

  def fourSumV1(nums: Array[Int], target: Int): List[List[Int]] = {

    val result = new ArrayBuffer[List[Int]]()

    //  Array legitimacy 
    if (nums == null) {
      return result.toList
    }

    //  Length validity 
    val length = nums.length
    if (length < 4) {
      return result.toList
    }

    //  Array sorting 
    val sortedNums = nums.sorted

    breakable {
      (0 to length - 4).filter(first => { //  Use  filter  Instead of  continue
        !(first > 0 && sortedNums(first) == sortedNums(first - 1)) &&
        !(sortedNums(first) + sortedNums(length - 3) + sortedNums(length - 2) + sortedNums(length - 1) < target)
      }).foreach(first => {

        //  The smallest four numbers exceed  target
        if (sortedNums(first) + sortedNums(first + 1) + sortedNums(first + 2) + sortedNums(first + 3) > target) {
          break()
        }

        breakable {
          (first + 1 to length - 3).filter(second => { //  Use  filter  Instead of  continue
            !(second > first + 1 && sortedNums(second) == sortedNums(second - 1)) &&
              !(sortedNums(first) + sortedNums(second) + sortedNums(length - 2) + sortedNums(length - 1) < target)
          }).foreach(second => {

            if (sortedNums(first) + sortedNums(second) + sortedNums(second + 1) + sortedNums(second + 2) > target) {
              break()
            }

            var left = second + 1
            var right = length - 1

            while (left < right) { //  Judge  sum  And  target  The relationship between 

              val sum: Long = sortedNums(first) + sortedNums(second) + sortedNums(left) + sortedNums(right)

              if (sum.equals(target.toLong)) {
                result.append(Array(sortedNums(first), sortedNums(second), sortedNums(left), sortedNums(right)).toList)

                while (left < right && sortedNums(left) == sortedNums(left + 1)) {
                  left += 1
                }
                left += 1

                while (left < right && sortedNums(right) == sortedNums(right - 1)) {
                  right -= 1
                }
                right -= 1
              } else if (sum < target) {
                left += 1
              } else {
                right -= 1
              }
            }
          })
        }
      })
    }

    result.toList
  }

C. Execution efficiency

BBQ 了 , The last few examples overturned , Take the test nums and target Try it locally ：

   val int: Int = 1000000000 + 1000000000 + 1000000000
   println(int)

The result is -1294967296,Int The maximum value is  2147483647, Here are three 1000000000 The sum exceeds Int Scope thus leads to sum The result is abnormal , Thereby affecting sum And target The judgment of the . 

D. Repair

scala If Long + Int You'll get Long, Based on the above cross-border problem , We are sum When will nums(start) Convert to Long, then target Convert to Long, At this time, there will be no array out of bounds ：

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks.{break, breakable}

object Solution {
    def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
    val result = new ArrayBuffer[List[Int]]()

    if (nums == null) {
      return result.toList
    }

    val length = nums.length
    if (length < 4) {
      return result.toList
    }

    val sortedNums = nums.sorted

    breakable {
      (0 to length - 4).filter(first => {
        !(first > 0 && sortedNums(first) == sortedNums(first - 1)) &&
          !(sortedNums(first).toLong + sortedNums(length - 3) + sortedNums(length - 2) + sortedNums(length - 1) < target.toLong)
      }).foreach(first => {

        //  The smallest four numbers exceed  target
        if (sortedNums(first).toLong + sortedNums(first + 1) + sortedNums(first + 2) + sortedNums(first + 3) > target.toLong) {
          break()
        }

        breakable {
          (first + 1 to length - 3).filter(second => {
            !(second > first + 1 && sortedNums(second) == sortedNums(second - 1)) &&
              !(sortedNums(first).toLong + sortedNums(second) + sortedNums(length - 2) + sortedNums(length - 1) < target.toLong)
          }).foreach(second => {

            if (sortedNums(first).toLong + sortedNums(second) + sortedNums(second + 1) + sortedNums(second + 2) > target.toLong) {
              break()
            }

            var left = second + 1
            var right = length - 1

            while (left < right) {

              //  first place  toLong target toLong
              val sum = sortedNums(first).toLong + sortedNums(second) + sortedNums(left) + sortedNums(right)

              if (sum.equals(target.toLong)) {
                result.append(Array(sortedNums(first), sortedNums(second), sortedNums(left), sortedNums(right)).toList)

                while (left < right && sortedNums(left) == sortedNums(left + 1)) {
                  left += 1
                }
                left += 1

                while (left < right && sortedNums(right) == sortedNums(right - 1)) {
                  right -= 1
                }
                right -= 1
              } else if (sum < target.toLong) {
                left += 1
              } else {
                right -= 1
              }
            }
          })
        }
      })
    }

    result.toList
    }
}

This time it passed perfectly ~ 

5、 ... and .N Sum of the numbers

I mentioned two numbers before 、 Tricount 、 Sum of four numbers , This can be done according to the mathematical induction of Mathematics N The reasoning of the sum of numbers .

1. prove

First, sort the array

K = 1 when , The sum of a number , This direct traversal judgment can , No problem

K = N when , Before fixation N-2 position , Double pointer to the last two bits , The above has been implemented and verified

When K = N+1 when , in the light of nums Every number in num And its index index, take K=N+1 Convert to  K= N The problem of :

nums(1) + nums(2) + ... + nums(index) + ... + nums(N+1) = target (K=N+1)

                                                 Convert to ↓ 

nums(1) + nums(2) + ... + nums(N+1) = target - nums(index) (K=N)

Just convert N+1 individual K=N The answers to the questions are summarized into one List in , That is to say K=N+1 Time solution , Certificate completion .

2. Summary statement

When K=N when , Before fixation N-2 position , The last two bits are traversed by double pointers , Can solve Target problem .

6、 ... and . summary

With N The increase of , In addition to the increased time complexity of the loop , More pruning conditions also need to be considered , for example target=0 when start Element is greater than 0 、 The first few elements sum It's over target etc. , Filtering out these conditions can improve the running speed . besides ,Scala Not supported by default continue And break Method , therefore python、java Many steps can be directly continue Easy skip , and scala We need to pay attention to breakable Surrounded by the function body and when and where break, Relatively speaking, we need to control logic more clearly , Students in need can refer to ：Scala/Java - break & continue.