【笔记】Leetcode题目：“两数之和”，“两数相加”

昨天做了 Leetcode 上的两道题目，”两数之和“，“两数相加”。

第一道题：两数之和
难度：简单
代码用时：4ms
占用内存：15.5MB
语言：PHP
题目链接：https://leetcode-cn.com/problems/two-sum

题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

思路：

使用 for （$i）循环，令 $x 等于 $nums[$i] , 查询 $target-$nums[$i] 在 $nums 中是否存在，存在则返回下标给 $key 不存在（为 null 但不为 0）则跳过循环。
存在的情况下，再从下标为 $key 开始使用 for （$ii）循环，当 $nums[$ii]+$x==$target 且下标 $ii 不等于 $i 时，返回数组 [$i,$ii] 即可。

代码如下：

<?php
class Solution {
    public function twoSum($nums, $target) {
        $len = count($nums);
        for ($i=0;$i<=$len-1;$i++){
            $x = $nums[$i];
            $y = $target - $x;
            $key = array_search($y,$nums);
            if ($key == null and $key !== 0){
                continue;
            }else{
                for ($ii=$key;$ii<=$len-1;$ii++){
                    if ($nums[$ii]+$x==$target and $ii != $i){
                        return [$i,$ii];
                    }else{
                        continue;
                    }
                }
            }
        }
    }
}
?>

提交结果如下图：

第二道题：两数相加
难度：中等
代码用时：8ms
占用内存：15.1MB
语言：PHP
题目链接：https://leetcode-cn.com/problems/add-two-numbers/

题目：
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

思路：

首先我们需要了解“链表”类（ListNode）。
然后根据类进行计算。
1.计算顺序，因为题目要求满 10 进 1，向右进一，所以我们从左向右算起。
2.计算方法，采用 while 循环对每一节考虑。令 $l1 等于链表 1 的每一节，$value1 等于链表 1 每一节的值，每执行一次 value 的赋值，就令 $l1 等于下一个节。链表 2 同理。$sum 等于 $value1 和 $value2 的和。$last 是进位值，$sum 大于等于 10 时为 1，小于 10 时为 0。$new 是新的链节，当 $sum 大于等于 10 时，将 $sum-10 储存在链节，并给 $last 赋值为 1，进而记作下一节计算时的进位 1；当 $sum 小于 10 时，将 $sum 储存在链节中并给 $last 赋值为 0，进而记作下一节计算时的进位 0。

代码如下：

<?php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $result = '';
        $new = &$result;
        $last = 0;
        while (true){
            //如果最后一位相加满10，将进位1（last变量的值）记作链节的值
            if ($l1 == null and $l2 == null){
                if ($last){
                    $new = new ListNode($last);
                }
                break;
            }
            //如果l1链节的值不为空 l1链节的值赋值给value1变量，否则为0
            if ($l1 != null){
                $value1 = $l1->val;
                $l1 = $l1->next;
            }else{
                $value1 = 0;
            }
            //同理l1链节
            if ($l2 != null){
                $value2 = $l2->val;
                $l2 = $l2->next;
            }else{
                $value2 = 0;
            }
            $sum = $value1 + $value2 + $last;
            //如果总和满10，减去10的值记为新链节的值，进位1赋值给last变量，不满10，直接作为新链节的值，进位0赋值给last变量
            if ($sum >= 10){
                $new = new ListNode($sum-10);
                $last = 1;
            }else{
                $new = new ListNode($sum);
                $last = 0;
            }
            $new = &$new->next;
        }
        return $result;
    }
}
?>

提交结果如下图：