Pastebin: array of integers, sum two integers that match a certain value. #2

Formato

Plain text

Post date

2022-07-05 02:44

Publication Period

Unlimited

 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
 
 You may assume that each input would have exactly one solution, and you may not use the same element twice.
 
 You can return the answer in any order.
 
  
 
 Example 1:
 
 Input: nums = [2,7,11,15], target = 9
 Output: [0,1]
 Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
 
 Example 2:
 
 Input: nums = [3,2,4], target = 6
 Output: [1,2]
 
 Example 3:
 
 Input: nums = [3,3], target = 6
 Output: [0,1]
 
  
 
 Constraints:
 
     2 <= nums.length <= 104
     -109 <= nums[i] <= 109
     -109 <= target <= 109
     Only one valid answer exists.
 
  
 Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
 
 
 -----------------
 
 A trivial O(n^2) solution in PHP could be:
 
     function twoSum($nums, $target) {
         for ($pos1 = 0; $pos1 < count($nums) - 1 ; $pos1++) {
             for ( $pos2 = $pos1+1 ; $pos2 < count($nums); $pos2++) {
                 $sum = $nums[$pos1] + $nums[$pos2];
                 if ( $sum == $target) {
                     return array ($pos1, $pos2);
                 }
             }
         }
     }
 
 -------------
 
 class Solution {
 
     /**
      * @param Integer[] $nums
      * @param Integer $target
      * @return Integer[]
      */
     function twoSum($nums, $target) {
         #$original_nums = $nums; #copy to maintain the original indexes, we need those.
                                 # this is O(n)
                                 # but then the search may be O(n) too as it is not ordered
                                 # a better idea is to switch keys and values
                                 # so that with the values we can reach the keys.
                                 
         $orig_num_flipped = array_flip($nums); 
           # the flip, values are now keys and viceversa, 
           # should cost O(2n)=O(n) as well. We get a new array. 
           # update: doesn't work if a value is replicated, 
           # then if a number is there multiple times it will be associated with the larger key.
         
         sort($nums); # this should be O(n*log(n)), merge sort, happens in place
         
         # then thanks to the fact that we need exactly 2 numbers,
         # for the property of the sum, we know that
         # target = x+y and if x and y are big, then at most x=y=target/2
         # otherwise x (or y) may start from the smallest number up to target/2 and y
         # may start from target-x down to target/2
         # then we have it.
         # That is O(n)
         # then between O(n*log(n)) and O(n), O(n*log(n)) should lead.
         # the problem is to identify the element in the sorted array that is closer to target.
         
         # otherwise one has to first start from the biggest element and get down to target,
         # then start the check (the complexity remains O(n) though)
         
         $upper_pos = count($nums);
         for ($pos1 = count($nums)-1 ; $pos1 > -1 ; $pos1--) {
             # here we identify the first element smaller than target
             if ($nums[$pos1] < $target) {
                 $upper_pos = $pos1;
                 break;
             }
         }
         
         for ( $pos_low=0, $pos_up = $upper_pos ; $pos_low < $pos_up ; ) {
             # here we try to identify both elements.
             $sum = $nums[$pos_low] + $nums[$pos_up];
             print ($sum);
             if ($sum == $target) {
                 return array( $orig_num_flipped[$nums[$pos_low]], $orig_num_flipped[$nums[$pos_up]] );
                     # nope this doesn't work. the problem is that with the sort
                     # the association with the original indexes is lost.
                     # if the function uses the array_flip function, to make an extra array
                     # where the values are the keys, same values go overwrite the original key
                     # keeping the largest one.
                     # To work it is needed to have a sort function that "sorts" also the keys
                     # a bit like KSORT in userRPL (listExt library)
                     # With a KSORT function the entire procedure would have taken
                     # at most O(n*logn) as the heaviest part would be the sorting.
             }
             else {
                 # pay attention here, defensive approach
                 if ($sum < $target) {
                     # then we presume pos_up can be still be good, and we increment pos_low
                     $pos_low++;
                 }
                 else {
                     #then we overshoot, pos_up has to come down
                     $pos_up--;
                 }
             }
         }
     }
 }