Two Sum & Add Two Numbers Singly linked list leetcode solution explanation
This code solves the Two Sum problem: given an array of integers (nums) and a target sum (target), the goal is to find two indices in the array such that the numbers at these indices add up to the target.
Explanation:
Initialization:
visited is a HashMap Integer, Integer used to store each number (nums i ) and its corresponding index (i) as we iterate through the array. This allows for fast lookups to check if the complement (target - current number) has already been seen.
result is an integer array of size 2 that will store the indices of the two numbers that sum up to the target.
Loop through the array:
The loop iterates over each element in nums using its index i.
For each element nums i , the algorithm calculates val, which is the complement (i.e., the value that, when added to nums i , would give the target sum). This is done by int val = target - nums i .
Check for the complement:
If the complement val is already present in the visited map (i.e., if visited.containsKey(val) is true), it means the complement has been encountered earlier in the array.
In this case, the result is updated to store the indices of the two numbers:
visited.get(val) gives the index of the previously encountered complement.
i is the index of the current number (nums i ).
The result array is returned immediately because the problem guarantees that exactly one solution exists.
Update the visited map:
If the complement val is not found, the current number nums i is added to the visited map with its index (i).
Return the result:
If the loop completes without returning early, the result will still contain the correct indices because the problem guarantees a solution. However, the return result; at the end is a fallback in case no solution is found (though this won't happen with the problem's guarantee).
Example:
If nums = 2, 7, 11, 15 and target = 9:
At index 0 (nums 0 = 2), the complement is 9 - 2 = 7. Since 7 is not in the visited map, 2 is added to the map: visited = (2: 0).
At index 1 (nums 1 = 7), the complement is 9 - 7 = 2. Since 2 is in the visited map, the indices 0, 1 are returned because 2 and 7 add up to 9.
This code is solving the Add Two Numbers problem, where two numbers are represented as linked lists, and each node contains a single digit. The goal is to return the sum of these two numbers, also as a linked list. Each number is stored in reverse order, meaning the ones place is at the head of the list, the tens place is the second node, and so on.
Breakdown:
Node class:
Node is a class that represents a node in a singly linked list, where each node contains a val (value) and a next (pointer to the next node).
The input lists l1 and l2 represent the two numbers.
Dummy node initialization:
A dummy node is created to act as the starting point for the result list. It's initialized with a value of 0.
current is a pointer to the dummy node. This pointer will traverse the new list as new nodes are added.
Carry variable:
carry is initialized to 0 and will store the carry-over when the sum of two digits is greater than or equal to 10.
While loop:
The loop continues until both l1 and l2 are null, meaning all digits from both numbers have been processed.
In each iteration:
The value of the current node in l1 is assigned to x. If l1 is null (i.e., one list is shorter than the other), x is set to 0.
Similarly, the value of the current node in l2 is assigned to y. If l2 is null, y is set to 0.
The sum of x, y, and carry is computed as sum = carry + x + y.
The carry is updated to sum / 10 (i.e., the tens digit of the sum, which will be carried over to the next digit).
A new node is created with the value sum % 10 (i.e., the ones digit of the sum), and this node is added to the result list by updating current.next.
current is then moved to this new node (current = current.next).
l1 and l2 are moved to the next nodes in their respective lists (l1 = l1.next, l2 = l2.next).
Handling the final carry:
After the loop, if there is any carry left (i.e., if carry 0), a new node is created with this carry value and added to the result list.
Return the result:
The method returns dummy.next, which is the head of the result linked list. The dummy node itself is a placeholder and is not part of the actual result.
Example:
Let's assume we have the two linked lists representing the numbers 342 and 465, where the numbers are in reverse order:
rust
Copy code
l1 = [2 - 4 - 3] (342)
l2 = [5 - 6 - 4] (465)
The addition process would look like this:
Add the first digits: 2 + 5 = 7 (no carry). The result is [7].
Add the second digits: 4 + 6 = 10. Set the carry to 1, and the result is [7 - 0].
Add the third digits: 3 + 4 + 1 (carry) = 8. The result is [7 - 0 - 8].
So, the final linked list represents the number 807 (which is the sum of 342 and 465).
Смотрите видео Two Sum & Add Two Numbers Singly linked list leetcode solution explanation онлайн, длительностью часов минут секунд в хорошем качестве, которое загружено на канал CodeWis Technologies by Nuhman Paramban 11 Сентябрь 2024. Делитесь ссылкой на видео в социальных сетях, чтобы ваши подписчики и друзья так же посмотрели это видео. Данный видеоклип посмотрели 12 раз и оно понравилось 1 посетителям.
