leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

0001-two-sum.rs (1998B)

      1/// 1. Two Sum (Easy)
      2///
      3/// Given an array of integers nums and an integer target, return indices of the
      4/// two numbers such that they add up to target.
      5///
      6/// You may assume that each input would have exactly one solution, and you may
      7/// not use the same element twice.
      8///
      9/// You can return the answer in any order.
     10///
     11///   Example 1:
     12///
     13///   Input: nums = [2,7,11,15], target = 9
     14///   Output: [0,1]
     15///   Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
     16///
     17///   Example 2:
     18///
     19///   Input: nums = [3,2,4], target = 6
     20///   Output: [1,2]
     21///
     22///   Example 3:
     23///
     24///   Input: nums = [3,3], target = 6
     25///   Output: [0,1]
     26///
     27///   Constraints:
     28///
     29///     * 2 <= nums.length <= 104
     30///     * -109 <= nums[i] <= 109
     31///     * -109 <= target <= 109
     32///     * Only one valid answer exists.
     33///
     34/// Follow-up: Can you come up with an algorithm that is less than O(n2) time
     35/// complexity?
     36use leetcode::*;
     37
     38struct Solution {}
     39
     40impl Solution {
     41    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
     42        let mut nums: Vec<_> = nums.iter().enumerate().collect();
     43        nums.sort_by(|(_ai, a), (_bi, b)| a.cmp(b));
     44        let mut i = 0usize;
     45        let mut k = nums.len() - 1;
     46        let mut result = Vec::new();
     47        loop {
     48            if nums[i].1 + nums[k].1 == target {
     49                break;
     50            } else if nums[i + 1].1 + nums[k].1 <= target {
     51                i += 1;
     52            } else {
     53                k -= 1;
     54            }
     55        }
     56        result.push(nums[i].0 as i32);
     57        result.push(nums[k].0 as i32);
     58        result
     59    }
     60}
     61
     62pub fn main() {
     63    println!("{:?}", Solution::two_sum(arg_into(1), arg_into(2)))
     64}
     65
     66#[cfg(test)]
     67mod tests {
     68    use crate::Solution;
     69    use leetcode::vi;
     70
     71    #[test]
     72    fn test() {
     73        assert_eq!(Solution::two_sum(vi("[2,7,11,15]"), 9), vi("[0,1]"));
     74        assert_eq!(Solution::two_sum(vi("[3,2,4]"), 6), vi("[1,2]"));
     75        assert_eq!(Solution::two_sum(vi("[3,3]"), 6), vi("[0,1]"));
     76    }
     77}