Hướng dẫn two sum leetcode solution javascript - hai giải pháp leetcode tổng hợp javascript

Giới thiệu

LeetCode. Một sự thật đáng tiếc của cuộc sống nhà phát triển là đối với một số cuộc phỏng vấn việc làm, cần phải học cấu trúc dữ liệu và thuật toán (DSA) theo một cách cụ thể. Một cách mà bạn dự kiến ​​sẽ mã hóa một giải pháp cho vấn đề DSA nơi bạn sẽ google nó.

Tôi nói _ không may _ bởi vì trong hầu hết các trường hợp, việc biết họ ở mức độ cần thiết cho các cuộc phỏng vấn kỹ thuật là không cần thiết và hầu như không phản ánh khả năng công việc thực tế._unfortunate _ because in most cases it is unnecessary to know them to the degree required for the technical interviews and hardly reflects actual job capability.

Nhưng tôi lạc đề, LeetCode là một trang web tổng hợp hàng tấn các vấn đề DSA khác nhau. Tôi sẽ trải qua một số vấn đề LeetCode trong tháng tới, giải thích và giải quyết chúng, để giúp đỡ người khác. Và nó cũng giúp tôi viết lại giải pháp. 😎

Lời nhắc

Đưa ra một loạt các số nguyên & nbsp; ________ 7 & nbsp; và một số nguyên & nbsp; ____ ____ 8, return & nbsp; chỉ số của hai số mà chúng cộng vào & nbsp; ________ 8. Bạn có thể cho rằng mỗi đầu vào sẽ có & nbsp; chính xác & nbsp; một giải pháp và bạn không được sử dụng & nbsp; cùng & nbsp; phần tử hai lần. Bạn có thể trả lại câu trả lời theo bất kỳ thứ tự nào.exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Ví dụ 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Suy nghĩ thông qua

Đây là vấn đề LeetCode đầu tiên và khá dễ dàng. Điều đầu tiên xuất hiện trong tâm trí chỉ là lặp lại trên mảng hai lần và tìm ra số tiền cần thiết. Điều này sẽ 100% cho chúng tôi giải pháp.

Tuy nhiên, như nhiều bạn có thể biết về các loại câu hỏi này. Thông thường, nó không đủ để đúng. Đối với các vấn đề DSA, bạn muốn có hiệu quả nhất có thể.efficient as possible.

Vì vậy, ví dụ, giải pháp đầu tiên của chúng tôi sẽ là một cái gì đó dọc theo các dòng này:

Trong đó

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

Giải pháp đầu tiên

Tôi chủ yếu sử dụng JavaScript để giải pháp sẽ trông giống như thế này:

JavaScript
const twoSum(nums, target) {
    for(let i = 0;  i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if(j === i) continue;
            if((nums[i] + nums[j]) === target) return [i, j];
        }
    }
}

nums là mảng số và target là giải pháp mong muốn. Tôi lặp lại trên cả hai mảng và kiểm tra xem tổng là giá trị cần thiết. Tuy nhiên, như đã nêu trong lời nhắc, chúng ta không nên sử dụng cùng một phần tử hai lần.

Vì vậy, chúng tôi có thể kiểm tra xem các lần lặp có ở cùng một phần tử không và bỏ qua:

JavaScript
if(j === i) continue;

Tuy nhiên, như tôi đã đề cập trước đây là điều này rất không được tối ưu hóa.

Giải pháp thứ hai

Một giải pháp tốt hơn nhiều sẽ là tìm kiếm mục tiêu dựa trên số hiện tại. Điều đó nghĩa là gì?current number. What does that mean?

Ví dụ: khi bạn lần đầu tiên bắt đầu lặp lại trên mảng, bạn biết số chính xác mà bạn đang tìm kiếm. Số bạn đang tìm kiếm là kết quả của phép trừ mục tiêu và giá trị lặp hiện tại.result of the subtraction of the target and the current iterated value.

Hãy lấy mảng đầu tiên của chúng tôi làm ví dụ.

Khi chúng tôi ở phần tử đầu tiên

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

Giới thiệu một bảng băm.

Bàn băm

Bảng băm là một cấu trúc dữ liệu ánh xạ khóa cho các giá trị. Điều này là hoàn hảo cho trường hợp sử dụng của chúng tôi bởi vì chúng tôi chỉ muốn ánh xạ

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

Nhưng làm thế nào để chúng ta tạo ra bảng băm này?

Bản đồ là một đối tượng tích hợp JavaScript. Điều duy nhất bạn cần biết là nó giữ các cặp giá trị khóa và có API để nhanh chóng kiểm tra nội dung:

function twoSum(nums, target) {let numObj = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (numObj[complement] !== undefined) {
      return [numObj[complement], i];
    }
    numObj[nums[i]] = i;
  }
}

function twoSum(nums, target) {let numObj = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (numObj[complement] !== undefined) {
      return [numObj[complement], i];
    }
    numObj[nums[i]] = i;
  }
}

function twoSum(nums, target) {let numObj = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (numObj[complement] !== undefined) {
      return [numObj[complement], i];
    }
    numObj[nums[i]] = i;
  }
}

Giải pháp thứ hai

JavaScript
const hashTable = new Map();

for(let i = 0; i < nums.length; i++) {
  const num = nums[i];
  const substractionWeWant = target - num;

  if (hashTable.has(substractionGoal) {
      return [i, hashTable.get(substractionGoal)];
  } else {
      hashTable.set(num, i);
  }
}

Bây giờ chúng tôi có một cách đơn giản hóa để kiểm tra các giá trị trước đó. Quay trở lại mã trước tiên chúng tôi thực hiện một lần lặp duy nhất của vòng lặp. Bằng cách trừ đi giá trị target khỏi giá trị chỉ mục hiện tại

function twoSum(nums, target) {let numObj = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (numObj[complement] !== undefined) {
      return [numObj[complement], i];
    }
    numObj[nums[i]] = i;
  }
}

Vì vậy, để nhắc lại

1. Chúng tôi lặp qua mảng
2. Chúng tôi kiểm tra xem bản đồ giá trị hiện tại của chúng tôi có phép trừ target và giá trị hiện tại mà chúng tôi đang lặp lại không. Nếu chúng ta trả về cả chỉ mục của giá trị hiện tại và chỉ mục của giá trị trong bản đồ của chúng ta
3. Nếu chúng tôi không tìm thấy một trận đấu, chúng tôi sẽ thêm nó vào bản đồ của mình và tiếp tục

Giải pháp đầu tiên:

Giải pháp thứ hai:

Gói nó lên

Nếu bạn muốn theo kịp loạt bài này, hãy theo dõi tôi ở đây hoặc bất kỳ phương tiện truyền thông xã hội nào của tôi dưới đây!

Nhiều nội dung hơn ở mã có thể tin cậy được

Hãy kết nối

Nếu bạn thích điều này, hãy kết nối với tôi trên LinkedIn hoặc Twitter

Kiểm tra lộ trình phát triển miễn phí của tôi và tin tức ngành công nghệ hàng tuần trong bản tin của tôi.

Nếu bạn thấy bất kỳ lỗi chính tả hoặc lỗi nào, bạn có thể chỉnh sửa bài viết trực tiếp trên GitHub

Hãy đứng đầu ngành công nghệ và phát triển như một nhà phát triển với một lựa chọn các bài báo và tin tức cùng với lời khuyên cá nhân, quan sát và hiểu biết. 🚀developer with a curated selection of articles and news alongside personal advice, observations, and insight. 🚀

Không có thư rác 🙅‍♂. Hủy đăng ký

.